A shuffle that looks fair and isn't

Ask a computer to shuffle three cards and it has six possible orders to land on. A very natural-looking program never lands on them equally often.

The obvious way to shuffle

Take a row of cards. Go along it from left to right. At each position, pick a random position anywhere in the row and swap the two cards. Every card gets visited and every swap is random, so the result should be random too.

for i from 0 to n-1:
    j = random(0 .. n-1)
    swap(cards[i], cards[j])

This is the naive shuffle. It is short, it looks fair, and it appears in real code. It is also biased, and the bias can be counted exactly.

Count the possibilities

With three cards the loop makes three random choices, each one of 3 positions. That gives 3 × 3 × 3 = 27 equally likely paths. But three cards have only 3! = 6 orders. Twenty-seven paths cannot be split evenly across six orders: 27 ÷ 6 is 4.5. Some orders must get 5 paths and some only 4.

In general the naive shuffle has nn paths and there are n! orders. For any deck bigger than two cards, n! does not divide nn, so the split is always uneven. Press the buttons below and watch it appear.

The bias grows with the deck. With four cards the naive shuffle has 4⁴ = 256 paths for 24 orders, where a fair share would be 10.67 paths each. Counting them all, the least likely order gets 8 paths and the most likely gets 15, so one order comes up almost twice as often as another. A real deck is far worse, and every one of its 52! orders has its own unequal share.

After a few thousand shuffles, the naive bars split into two groups. Three orders turn up about 18.5% of the time (5 of 27 paths) and the other three about 14.8% (4 of 27). A fair shuffle would give every order 16.7%. The gap is small, but it never goes away however many shuffles you run, and a card player or a lottery could be exploited with it.

The fix: shrink the pool

The repair is to stop picking from the whole row. Walk from the end, and at each step pick only from the cards not yet fixed in place:

for i from n-1 down to 1:
    j = random(0 .. i)
    swap(cards[i], cards[j])

Now the first choice has n options, the next has n−1, and so on. The number of paths is n × (n−1) × … × 1, which is exactly n!. Every path leads to a different order, so every order has exactly one path. For three cards that is 3 × 2 = 6 paths for 6 orders. Switch to Fisher–Yates in the lab and the bars settle at one sixth each.

Where it comes from

Ronald Fisher and Frank Yates described the pencil-and-paper version in 1938, in their book of statistical tables, using a table of random numbers. Richard Durstenfeld published the computer version above in 1964, as “Algorithm 235: Random permutation” in Communications of the ACM. Donald Knuth then spread it widely through The Art of Computer Programming. It is the standard way to shuffle today, and its cost is one pass over the cards.

A 52-card catch

A correct algorithm still needs a good source of randomness. A deck of 52 cards has 52! orders, about 2²²⁶. A random number generator with only 32 bits of internal state can start from just 2³² different places, so it can never reach more than a minuscule fraction of the possible decks, however fair the algorithm around it is.

So shuffling well takes two things: a method where every order has the same number of paths, and a random source big enough to reach them all.