3 ms·
For those who haven't seen it, here is how you can show with a counting and divisibility argument that a common algorithm many come up with to shuffle is not a
by tzs 8y ago
For those who haven't seen it, here is how you can show with a counting and divisibility argument that a common algorithm many come up with to shuffle is not a fair shuffle.
Here's the algorithm, in pseudo code (yes, with 1-based arrays!):
let a = [1, 2, 3, ...., N] # the items to shuffle
for i = 1 to N
j = random_in(1, N)
swap(a[i], a[j])
Imagine that random_in() makes a log of all its return values. In this program every time it is called it returns an integer >= 1 and <= N. It is called N times. Thus, the log consists of N integers with N possible values for each integer. In what follows we shall call such a log a trace of the program (because log could be confused for logarithm). (Trace has a meaning in linear algebra, but that should not cause a problem here).
That means that there are N^N distinct possible traces. Each of these traces is equally likely. We can associate with each of the traces a shuffle, namely the shuffle that results from the run of the program that produced that trace.
This gives us a list of N^N shuffles. This list will contain duplicates, because there are only N! distinct shuffles, and N! < N^N.
The shuffle is fair if and only if each possible shuffle occurs the same number of times in the list of N^N shuffles. For it to be even possible for that to happen, we must have N! divides N^N.
But if N > 2, that cannot happen. To show this note that if N! divides N^N, then every divisor of N! must divide N^N. Pick a prime P such that (1) p < N and (2) P does not divide N. Then p is a divisor of N! but is not a divisor of N^N, which shows that N! does not divide N^N, and so the shuffle is not fair.
Can we really always pick such a prime? Yes. If N is divisible by every prime p < N, then N-1 must be prime, but then N-1 is a prime < N that does not divide N.
Note that you cannot save this class of algorithm by doing more passes. Those just change the size of the trace from N^N to N^(kN) for some integer N. Nor can you save it by changing it to pick both indices at random for the swap instead of picking only one at random. That just changes N^N to (N^2)^N = N^(2N). As long as the random number generator is always asked for a number in {1, 2, ..., N} and it is called the same number of times every time the program is run, the trace size is going to be a power of N, and cannot be divide evenly by N!
Now we can see why Fisher-Yates might work. It asks for a random number up to N the first iteration, up to N-1 the second iteration, and so on. That means its trace is N! long. There is no problem dividing N! by N!. Since N!/N! = 1, if we can show that each shuffle is included, that will also show that each is included the same number of times, and hence that Fisher-Yates is fair.
All we have to do now to see that Fisher-Yates is fair is show that each shuffle can be produced by it. Given a desired shuffle, it is easy to construct the trace that results in it, and we are done.
- tzs 8y ago> Can we really always pick such a prime? Yes. If N is divisible by every prime p < N, then N-1 must be prime, but then N-1 is a prime < N that does not divide N. We don't actually need a prime. We just need something that divides N! but does not divide N. N-1 will do nicely.
- stcredzero 8y agoI just thought of it this way: You're implementing "n P n" which just reduces to n factorial. So you just have to show that your 1st iteration is choosing from n items, your 2nd iteration is choosing from (n - 1) items, ... the (n - 1)th iteration is choosing from 2 items. (Choosing from 1 item is a noop, of course.) All we have to do now to see that Fisher-Yates is fair is show that each shuffle can be produced by it. Given a desired shuffle, it is easy to construct the trace that results in it, and we are done. You mean: Given a desired shuffle, you show you can construct the only trace that results in it.