The Shuffle
The obvious way to shuffle a list is to walk it and swap each card with a card at any position at all. It is wrong, and the interesting part is that you do not need to run it to find out. For four cards it can take 256 different runs, and there are 24 orderings to land on, and 24 does not divide 256 — so some ordering must come up more often than another, whatever the random numbers do. Everything on this page is an exhaustive count rather than a measurement: every run, tallied, with no sampling anywhere.
The obvious shuffle is not fair, and you can settle it by counting
1 The obvious shuffle: walk the list and swap each card with any position at all
The naive shuffle: walk the list, and swap each position with any position at all.
4
- runs it can take
- 256
- orderings to land on
- 24
- runs per ordering
- 10.667…
24 does not divide 256. However good the random numbers are, the runs cannot be shared out equally between the orderings, so some ordering must come up more often than another.
2 Count every run it can take. There are n^n of them and n! orderings, and n! does not divide n^n
Every run, tallied. This is a count of all of them, not a sample of some.
| ordering | runs landing there | against fair |
|---|---|---|
| 0123 | 10 | -0.67 |
| 0132 | 10 | -0.67 |
| 0213 | 10 | -0.67 |
| 0231 | 14 | +3.33 |
| 0312 | 11 | +0.33 |
| 0321 | 9 | -1.67 |
| 1023 | 10 | -0.67 |
| 1032 | 15 | +4.33 |
| 1203 | 14 | +3.33 |
| 1230 | 14 | +3.33 |
| 1302 | 11 | +0.33 |
| 1320 | 11 | +0.33 |
The commonest ordering comes up 15 times and the rarest 8, a 1.88 times difference, counted over all 256 runs. First 12 shown.
3 Durstenfeld's: swap position i with one from i onward, which makes exactly n! runs
Durstenfeld’s: position i swaps only with i or below. That makes the choice at each step one smaller than the last, so the number of runs is exactly n factorial.
| ordering | runs landing there | against fair |
|---|---|---|
| 0123 | 1 | even |
| 0132 | 1 | even |
| 0213 | 1 | even |
| 0231 | 1 | even |
| 0312 | 1 | even |
| 0321 | 1 | even |
| 1023 | 1 | even |
| 1032 | 1 | even |
| 1203 | 1 | even |
| 1230 | 1 | even |
| 1302 | 1 | even |
| 1320 | 1 | even |
24 runs onto 24 orderings, one apiece. Not approximately one: exactly one, and the count says so without any random numbers being involved.
4 The same seed deals the same hand, and every hand is equally likely
Seeded, which is what a card room needs: the same seed deals the same hand, on any machine, for ever.
- the hand
- K Q A J
- dealt again
- K Q A J
- the next seed along
- J A Q K
Seed 12345 deals the same hand every time it is asked. Seed 12346 deals a different one, and neither is more likely than any other.
These ran in this browser when the page loaded. Each claim, whether it held, and the number behind it.
| claim | held | measured |
|---|---|---|
| the naive shuffle of 4 has 256 runs and 24 orderings, and 24 does not divide 256 | yes | 256 / 24 = 10.667, so they cannot come up equally often |
| counting all 256 runs, the commonest ordering comes up 15 times and the rarest 8 | yes | a 1.88x difference, with nothing random about it |
| Durstenfeld's has exactly n! runs onto n! orderings, one apiece, at n = 3, 4 and 5 | yes | every ordering exactly once, at every size checked |
| the naive shuffle is fair at n = 2 and at no larger size checked | yes | 4 runs, 2 orderings, 2 each -- and it fails from 3 up |
| the deal draws from i downward, matching the rule the census proves fair, over 500 seeds | yes | every seed agrees with the fair walk |
| the same seed deals the same hand, and a different one does not | yes | seed 12345 gives KQAJ twice; 12346 gives JAQK |
What is real here, and what is not
The bias is counted, not measured, and that is the whole argument
Every number in the first three panels comes from walking all n^n or n! runs and tallying the outcome of each. There is no sampling, no random number generator and no confidence interval anywhere in them, which is why the page can say a thing is impossible rather than unlikely. A histogram, at any number of trials, could only ever have said the counts looked uneven.
It stops at five cards because the enumeration is n to the n
Five cards is 3,125 runs and six would be 46,656, which is still fast; fifty-two is a number with ninety digits. The claim is therefore exactly what is enumerated: two through five. The divisibility argument holds for every n above two and needs no enumeration at all, and the page prints that arithmetic separately from the tally for exactly that reason.
The naive shuffle is fair at two cards, and saying so matters
At n=2 there are 4 runs and 2 orderings and each comes up twice, so the naive shuffle is perfectly fair. It fails from three cards up. A page that said the algorithm is simply broken would be easier to write and would be wrong, and the table shows the boundary rather than describing it.
mulberry32 is not a cryptographic generator
The seeded deal uses mulberry32, which is a small fast PRNG with a 32-bit state. It is repeatable, which is what this panel is about, and it is entirely predictable, which is what a real card room must not have. Anything dealing for money needs a generator whose next output cannot be worked out from its previous ones, and this is not one. The shuffle above it is fair; the numbers feeding it here are only unpredictable-looking.
Sources
- R. Durstenfeld, Algorithm 235: Random Permutation, Communications of the ACM 7(7), July 1964, page 420. The first in-place version, and the one everybody now means by the shuffle.
- R. A. Fisher and F. Yates, Statistical Tables for Biological, Agricultural and Medical Research, 1938. The paper-and-pencil ancestor the algorithm is usually named for.
- Logical Art, the studio this belongs to.