StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p><strong>An Empirical Approach.</strong> </p> <p>Let's implement the erroneous algorithm in Mathematica: </p> <pre><code>p = 10; (* Range *) s = {} For[l = 1, l <= 30000, l++, (*Iterations*) a = Range[p]; For[k = 1, k <= p, k++, i = RandomInteger[{1, p}]; temp = a[[k]]; a[[k]] = a[[i]]; a[[i]] = temp ]; AppendTo[s, a]; ] </code></pre> <p>Now get the number of times each integer is in each position: </p> <pre><code>r = SortBy[#, #[[1]] &] & /@ Tally /@ Transpose[s] </code></pre> <p>Let's take three positions in the resulting arrays and plot the frequency distribution for each integer in that position: </p> <p>For position 1 the freq distribution is: </p> <p><a href="https://i.stack.imgur.com/NUWia.png" rel="noreferrer"><img src="https://i.stack.imgur.com/NUWia.png" alt="enter image description here"></a></p> <p>For position 5 (middle) </p> <p><a href="https://i.stack.imgur.com/lbJ2e.png" rel="noreferrer"><img src="https://i.stack.imgur.com/lbJ2e.png" alt="enter image description here"></a></p> <p>And for position 10 (last): </p> <p><a href="https://i.stack.imgur.com/7Ndie.png" rel="noreferrer"><img src="https://i.stack.imgur.com/7Ndie.png" alt="enter image description here"></a></p> <p>and here you have the distribution for all positions plotted together: </p> <p><a href="https://i.stack.imgur.com/EOVuI.png" rel="noreferrer"><img src="https://i.stack.imgur.com/EOVuI.png" alt="enter image description here"></a></p> <p>Here you have a better statistics over 8 positions:</p> <p><a href="https://i.stack.imgur.com/zQSsu.png" rel="noreferrer"><img src="https://i.stack.imgur.com/zQSsu.png" alt="enter image description here"></a></p> <p><strong>Some observations:</strong></p> <ul> <li>For all positions the probability of "1" is the same (1/n).</li> <li>The probability matrix is symmetrical with respect to the big anti-diagonal</li> <li>So, the probability for any number in the last position is also uniform (1/n)</li> </ul> <p>You may visualize those properties looking at the starting of all lines from the same point (first property) and the last horizontal line (third property). </p> <p>The second property can be seen from the following matrix representation example, where the rows are the positions, the columns are the occupant number, and the color represents the experimental probability: </p> <p><a href="https://i.stack.imgur.com/ba1eL.png" rel="noreferrer"><img src="https://i.stack.imgur.com/ba1eL.png" alt="enter image description here"></a></p> <p>For a 100x100 matrix: </p> <p><a href="https://i.stack.imgur.com/khCPM.png" rel="noreferrer"><img src="https://i.stack.imgur.com/khCPM.png" alt="enter image description here"></a></p> <p><strong>Edit</strong> </p> <p>Just for fun, I calculated the exact formula for the second diagonal element (the first is 1/n). The rest can be done, but it's a lot of work. </p> <pre><code>h[n_] := (n-1)/n^2 + (n-1)^(n-2) n^(-n) </code></pre> <p>Values verified from n=3 to 6 ( {8/27, 57/256, 564/3125, 7105/46656} )</p> <p><strong>Edit</strong></p> <p>Working out a little the general explicit calculation in @wnoise answer, we can get a little more info. </p> <p>Replacing 1/n by p[n], so the calculations are hold unevaluated, we get for example for the first part of the matrix with n=7 (click to see a bigger image): </p> <p><a href="https://i.stack.imgur.com/YmSJR.png" rel="noreferrer"><img src="https://i.stack.imgur.com/YmSJR.png" alt="enter image description here"></a></p> <p>Which, after comparing with results for other values of n, let us identify some known integer sequences in the matrix: </p> <pre><code>{{ 1/n, 1/n , ...}, {... .., A007318, ....}, {... .., ... ..., ..}, ... ...., {A129687, ... ... ... ... ... ... ..}, {A131084, A028326 ... ... ... ... ..}, {A028326, A131084 , A129687 ... ....}} </code></pre> <p>You may find those sequences (in some cases with different signs) in the wonderful <a href="http://oeis.org/" rel="noreferrer">http://oeis.org/</a> </p> <p>Solving the general problem is more difficult, but I hope this is a start</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload