StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>What a lovely question! I wish I had a full answer.</p> <p>Fisher-Yates is nice to analyze because once it decides on the first element, it leaves it alone. The biased one can repeatedly swap an element in and out of any place.</p> <p>We can analyze this the same way we would a Markov chain, by describing the actions as stochastic transition matrices acting linearly on probability distributions. Most elements get left alone, the diagonal is usually (n-1)/n. On pass k, when they don't get left alone, they get swapped with element k, (or a random element if they are element k). This is 1/(n-1) in either row or column k. The element in both row and column k is also 1/(n-1). It's easy enough to multiply these matrices together for k going from 1 to n.</p> <p>We do know that the element in last place will be equally likely to have originally been anywhere because the last pass swaps the last place equally likely with any other. Similarly, the first element will be equally likely to be placed anywhere. This symmetry is because the transpose reverses the order of matrix multiplication. In fact, the matrix is symmetric in the sense that row i is the same as column (n+1 - i). Beyond that, the numbers don't show much apparent pattern. These exact solutions do show agreement with the simulations run by belisarius: In slot i, The probability of getting j decreases as j raises to i, reaching its lowest value at i-1, and then jumping up to its highest value at i, and decreasing until j reaches n.</p> <p>In Mathematica I generated each step with</p> <pre><code> step[k_, n_] := Normal[SparseArray[{{k, i_} -> 1/n, {j_, k} -> 1/n, {i_, i_} -> (n - 1)/n} , {n, n}]] </code></pre> <p>(I haven't found it documented anywhere, but the first matching rule is used.) The final transition matrix can be calculated with:</p> <pre><code>Fold[Dot, IdentityMatrix[n], Table[step[m, n], {m, s}]] </code></pre> <p><code>ListDensityPlot</code> is a useful visualization tool.</p> <p><strong>Edit (by belisarius)</strong></p> <p>Just a confirmation. The following code gives the same matrix as in @Eelvex's answer:</p> <pre><code>step[k_, n_] := Normal[SparseArray[{{k, i_} -> (1/n), {j_, k} -> (1/n), {i_, i_} -> ((n - 1)/n)}, {n, n}]]; r[n_, s_] := Fold[Dot, IdentityMatrix[n], Table[step[m, n], {m, s}]]; Last@Table[r[4, i], {i, 1, 4}] // MatrixForm </code></pre>

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