Shuffling

Probability Level 4

A set of $N$ distinct items can be arranged in $N!$ different ways. We wish to write a computer program that shuffles the items randomly. Here are two candidates:

Code 1

1
2
3

for a = 1 to N-1
   for b = a+1 to N
      with 50% probability, swap item a and item b.

Code 2

1
2
3

for a = 1 to N-1
   b = uniformly chosen number between a+1 and N (inclusive).
   swap item a and item b.

Which of these codes, if any, will produce all $N!$ possible arrangements with equal probabilities?

Only code 1 Only code 2 Both code 1 and code 2 Neither code 1 nor code 2

2 solutions

Arjen Vreugdenhil
Jun 27, 2017

Code 1 can produce every arrangement of the $N$ items, but they do not have the same probability.

The program makes a certain number ( $q$ ) of choices to swap or not to swap, so that there are $2^q$ equally likely runs of the code. The probability of finding a certain arrangement $\sigma$ is therefore an integer multiple of $1/2^q$ . However, the desired probability is $1/N!$ . Since for $N>2$ , the denominator $N!$ contains prime factors unequal to 2, this cannot be the desired distribution.

Consider for instance the case $N = 3$ . There are eight possible ways the code can run, but only six different arrangements. Working out the details, the eight possibilities are

1 2	`NNN: 123 NNY: 132 NYN: 321 NYY: 312 YNN: 213 YNY: 231 YYN: 312 YYY: 321`

Thus the arrangements 312 and 321 are twice more likely than the other four.

Code 2 is unable to produce every arrangement. At the beginning, the first element is swapped with some other element from the list. After that, there is no possibility for it to be swapped back to its original place. Therefore the code generates only (and all) the arrangements that do not start in 1.

It is not difficult to produce the correct code:

1
2
3

for a = 1 to N-1
   b = uniformly chosen number between a to N (inclusive).
   swap item a and item b.

Neither of these methods is especially efficient either.

What would be a good order N method to shuffle?

Steven Perkins - 3 years, 11 months ago

The last method is the most efficient. It makes $N-1$ independent choices, making for $N\cdot (N-1)\cdot \dots\cdot 3\cdot 2 = N!$ possible outcomes. For any permutation of $N$ items, there is precisely one way in which the program can generate it.

For instance, in order to shuffle $(1,2,3,4,5)$ into $(3,1,4,5,2)$ , the program must

swap the first with the third item, to obtain $(3,2,1,4,5)$ ;
swap the second item with the third, making $(3,1,2,4,5)$ ;
swap the third item with the fourth, resulting in $(3,1,4,2,5)$ ;
swap the fourth item with the last, resulting in $(3,1,4,5,2)$ .

Arjen Vreugdenhil - 3 years, 11 months ago

Yes, I see now that you included this method. Thanks!

Steven Perkins - 3 years, 11 months ago

Andrew Lamoureux
Aug 16, 2017

Suppose we input the alphabet: {'A', 'B', 'C', ..., 'Z'}.

algorithm 1 is unfair to outputs with 'A' in first position, because that requires surviving 25 swap attempts, having low probability $({1\over2})^{25} < {1\over{26}}$
algorithm 2 never puts 'A' in the first position

Shuffling

2 solutions

0 pending reports