What distribution do you get from this random random shuffle?

Question

The well-known Shuffle Fisher-Yates algorithm can be used to randomly rearrange an array A of length N:

For k = 1 to N Pick a random integer j from k to N Swap A[k] and A[j] 

A common mistake that I was repeatedly told not to make is the following:

 For k = 1 to N Pick a random integer j from 1 to N Swap A[k] and A[j] 

That is, instead of choosing a random integer from k to N, you select a random integer from 1 to N.

What happens if you make this mistake? I know that the resulting permutation is distributed unevenly, but I do not know what guarantees exist in what will result from the distribution. In particular, does anyone have an expression for probability distributions over the finite positions of elements?

Answer 1

The empirical approach.

Let the erroneous algorithm be implemented in Mathematica:

 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]; ] 

Now get the number of times each integer is in each position:

 r = SortBy[#, #[[1]] &] & /@ Tally /@ Transpose[s] 

We take three positions in the resulting arrays and construct a frequency distribution for each integer in this position:

For position 1, the frequency distribution:

For position 5 (middle)

And for position 10 (last):

and here you have a distribution for all positions built together:

Here you have the best statistics on 8 positions:

Some observations:

• For all positions, the probability of "1" is the same (1 / n).
• The probability matrix is ​​symmetric with respect to the large antidiagonal
• So, the probability for any number in the last position is uniformly (1 / n)

You can visualize those properties that look at the beginning of all lines from the same point (first property) and the last horizontal line (third property).

The second property can be seen from the following matrix representation example, where the rows represent the positions, the columns represent the passenger number, and the color represents the experimental probability:

For 100x100 matrix:

Edit

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.

 h[n_] := (n-1)/n^2 + (n-1)^(n-2) n^(-n) 

Values ​​verified from n = 3 to 6 ({8/27, 57/256, 564/3125, 7105/46656})

Edit

By developing a slightly general explicit calculation in @wnoise's answer, we can get a little more information.

Replacing 1 / n with p [n], so the calculations are not evaluated, we get, for example, for the first part of the matrix with n = 7 (click to see a larger image):

which, comparing the results with other values ​​of n, we define some known integer sequences in the matrix:

 {{ 1/n, 1/n , ...}, {... .., A007318, ....}, {... .., ... ..., ..}, ... ...., {A129687, ... ... ... ... ... ... ..}, {A131084, A028326 ... ... ... ... ..}, {A028326, A131084 , A129687 ... ....}} 

You can find these sequences (in some cases with different signs) at the wonderful http://oeis.org/

Solving a common problem is harder, but I hope this is the beginning

Answer 2

The “common mistake” you mentioned is shuffling random transpositions. This problem was studied in detail by Deaconess and Shahshahani in Generating Random Permutation with Random Transpositions (1981) . They conduct a complete analysis of stopping time and rapprochement with uniformity. If you cannot get a link to the paper, please send me an email and I can send you a copy. This is a really fun read (like most of Percy Deacon’s work).

If the array has duplicate entries, the problem is slightly different. As a shameless plugin, this more general problem is addressed by me, Deaconess and Sanararajan in Appendix B Rule of thumb for shuffling a riffle (2011) .

Answer 3

Let's say

• a = 1/N
• b = 1-a
• B _i (k) - probability matrix after i swaps for the k th element. those. the answer to the question "where k after i swaps?". For example, B ₀ (3) = (0 0 1 0 ... 0) and B ₁ (3) = (a 0 b 0 ... 0) . You want B _N (k) for every k.
• K _i is the NxN matrix with 1s in the i-th column and i-th row, zero everywhere, for example:

• i _i is the identity matrix, but with the zero element x = y = i. For example, for i = 2:

• A _i is

Then

But since B _N (k = 1..N) forms a unit matrix, the probability that any given element i will be at the end in position j is determined by the matrix element (i, j) of the matrix:

For example, for N = 4:

Like a chart for N = 500 (color levels have a probability of 100 *):

The figure is the same for all N> 2:

• the most likely end position for the kth element is k-1 .
• the least probable end position is k for k <N * ln (2) , position 1 otherwise

Answer 4

I knew I saw this question before ...

“ why does this simple shuffling algorithm produce biased results? what is the simple reason? ” the answers have a lot of good, especially the link to Jeff Atwood’s horror coding blog .

As you might have guessed, based on @belisarius's answer, the exact distribution is highly dependent on the number of elements to be shuffled. Here's the Atwood graph for a 6-element deck:

Answer 5

What a wonderful question! I wish I had a complete answer.

Fisher-Yates is nice to analyze because when it solves the first element, it leaves it alone. An addicted person can repeatedly change an element anywhere.

We can analyze this in the same way as the Markov chain, describing actions as stochastic transition matrices acting linearly on probability distributions. Most of the elements remain alone, the diagonal is usually (n-1) / n. In passage k, when they are not alone, they exchange elements k (or a random element if they are element k). This is 1 / (n-1) in row or column k. The element in both row and column k is also 1 / (n-1). It is easy enough to multiply these matrices together for k, going from 1 to n.

We know that an element in the last place will be equally likely initially, because the last pass replaces the last place equally likely with any other. Similarly, the first element will be equally placed anywhere. This symmetry is that transposition changes the order of matrix multiplication. In fact, the matrix is ​​symmetric in the sense that the row i coincides with the column (n + 1 - i). In addition, the figures do not show much of the obvious picture. These exact solutions are consistent with the simulations performed by belisarius: In slot i. The probability of obtaining j decreases with increasing j to i, reaching the lowest value at i-1, and then jumping to the highest value in i and decreasing until j reaches n.

In Mathematica, I generated every step with

  step[k_, n_] := Normal[SparseArray[{{k, i_} -> 1/n, {j_, k} -> 1/n, {i_, i_} -> (n - 1)/n} , {n, n}]] 

(I did not find it documented anywhere, but the first matching rule is used.) The final transition matrix can be calculated using:

 Fold[Dot, IdentityMatrix[n], Table[step[m, n], {m, s}]] 

ListDensityPlot is a useful visualization tool.

Edit (by belisarius)

Just a confirmation. The following code gives the same matrix as @Eelvex's answer:

 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 

Answer 6

The Shuffle Fisher-Yates Wikipedia page has a description and an example of what will happen in this case.

Answer 7

You can calculate the distribution using stochastic matrices . Let the matrix A (i, j) describe the probability that the card initially at position i ends at position j. Then the kth swap has the matrix Ak given by Ak(i,j) = 1/N if i == k or j == k , (the card at position k can end anywhere, and any card can be at position k with equal probability), Ak(i,i) = (N - 1)/N for all i != k (each other card will remain in one place with probability (N-1) / N), and all other elements are equal to zero .

The result of the full shuffle is then given by the product of the matrices AN ... A1 .

I expect you to look for an algebraic description of probabilities; you can get it by expanding the above matrix product, but I think it will be quite complicated!

UPDATE: I just noticed the wnoise answer equivalent above! oops ...

Answer 8

I studied this further, and it turns out that this distribution has been studied in detail. The reason this is of interest is because this “broken” algorithm is used (or used) in the RSA chip system.

In mixing semi-invariant transpositions , Elchanan Mossel, Yuval Perez and Alistair Sinclair study this and a more general class of shuffles. The result of this article is that in order to achieve an almost random distribution, log(n) broken shuffles are required.

In the bias of the three pseudo-random shuffles (Aequationses Mathematicae, 22, 1981, 268-292), Ethan Bolker and David Robbins analyze this random case and determine that the total distance of variation to uniformity after one pass is 1, which indicates that this is not entirely random. They also give asymptotic analyzes.

Finally, Laurent Saloff-Coast and Jessica Zuniga found a good upper bound in the study of inhomogeneous Markov chains.

Answer 9

This question will ask for an interactive visual matrix diagram of the analysis of broken shuffle. Such a tool is on the page. Will it move? “Why random comparators are bad with Mike Bostock.”

Bostock has put together a great tool that analyzes random comparators. From the drop-down list on this page, select naive swap (random ↦ random) to see the broken algorithm and the template that it creates.

His page is informative, as it allows you to see the immediate effects that a change in logic has with shuffled data. For example:

This matrix diagram using uneven and very biased shuffle is created using a naive swap (we select from "1 to N") with the following code:

 function shuffle(array) { var n = array.length, i = -1, j; while (++i < n) { j = Math.floor(Math.random() * n); t = array[j]; array[j] = array[i]; array[i] = t; } } 

But if we implement a non-biased shuffle, where we select from "k to N", we should see a diagram like this:

where the distribution is uniform and is created from code such as:

 function FisherYatesDurstenfeldKnuthshuffle( array ) { var pickIndex, arrayPosition = array.length; while( --arrayPosition ) { pickIndex = Math.floor( Math.random() * ( arrayPosition + 1 ) ); array[ pickIndex ] = [ array[ arrayPosition ], array[ arrayPosition ] = array[ pickIndex ] ][ 0 ]; } } 

Answer 10

The excellent answers so far have focused on distribution, but you also asked, "What happens if you make this mistake?" - this is what I have not seen, I will explain it:

The Shuffle Knuth-Fisher-Yates algorithm selects 1 out of n elements, then 1 out of n-1 remaining elements, and so on.

You can implement it with two arrays a1 and a2, where you remove one element from a1 and insert it into a2, but the algorithm does it in place (which means that it needs only one array), as explained here (Google: "Shuffling Algorithms Fisher-Yates DataGenetics ") is very good.

If you do not delete the items, they can be selected randomly, which leads to biased randomness. This is exactly what the second example that you describe does. In the first example, the Knut-Fisher-Yays algorithm, uses a cursor variable that runs from k to N, which remembers which items have already been taken, therefore, avoiding selecting items more than once.