A perfect coin and a biased shuffle

The essays before this one in its sequence are about the source of randomness: whether a generator’s numbers fall on planes, whether they pass tests, whether a generator’s long silence after a bad start, as in three hundred thousand outputs of nearly nothing, can be escaped. This one assumes the source is perfect. Every call returns a number chosen exactly uniformly and independently of everything before. The question is whether a program that uses such numbers correctly-looking can still produce a biased result, and the answer is that it can — in one of the simplest programs there is, shuffling a deck of cards.

The program in question is the one most people write first. Go through the deck from top to bottom, and for each position swap its card with the card at a position chosen at random from the whole deck. It looks thorough, since every card gets moved and every position is a possible target, and it is wrong. The order it produces is not uniform, and the reason is a divisibility fact so simple that it fits in one line.

Fifty-two cards, swapped the naive way #

How a correct shuffle should behave is well understood. A uniformly random order has, for instance, a longest increasing run of about twice the square root of the deck size, as the longest climb of a shuffle found, and repeated physical riffle shuffles approach uniformity suddenly, after about seven for a real deck, which is the cutoff that the forgetting that happens all at once explains. A program is supposed to reach uniformity in one pass, exactly. The bias of the naive pass can be computed exactly without simulating a single shuffle. Follow one card: at each step either its position is the one being swapped, in which case it moves to a random place, or its position is the random target, in which case it moves to the position being processed, or neither, in which case it stays. That is a small chain of probabilities, and running it through the 52 steps gives every card’s exact chance of ending in every place.

A fair shuffle would make the whole square one even shade. Instead there is a warm band running just beside the diagonal: every card below the top is most likely to end exactly one place above where it started — 35 per cent more likely than fair for the second card ending on top, and between a fifth and a quarter more likely for cards in the middle of the deck. Cards tend to avoid their own starting place, the middle card ending where it began 15 per cent less often than it should, and cards from the bottom are unlikely to reach the top, the bottom card arriving on top 26 per cent less often than fair. Two lines of the square are exactly even: the top card is equally likely to end anywhere, and every card is equally likely to end at the bottom.

The band has a mechanism. When the shuffle reaches the position just above a card, one time in 52 it picks that card’s position as the random target, and the card is lifted up by one into a position the shuffle has already finished with. From there only another card’s random choice can move it, and the pass is moving away from it. Each card therefore gets one particular chance to move up by exactly one place that no other single move enjoys, and the excess on the band is that chance.

For a game of cards, a 35 per cent excess on particular card-and-place pairs is an enormous edge. It is the kind of flaw that is invisible in casual play and immediately exploitable by anyone who knows it is there.

256 runs cannot be shared among 24 orders #

The proof that the shuffle cannot be fair needs no computation at all. With $n$ cards there are $n$ steps, and at each step the random choice is one of $n$ positions, so the program has $n^n$ possible runs, all equally likely. Each run produces one order of the cards. For every order to have chance $1/n!$, each order would have to be produced by exactly $n^n / n!$ runs — a whole number. But for $n \ge 3$ the number $n - 1$ is at least 2 and shares no prime factor with $n$, so any prime dividing $n - 1$ divides $n!$ and does not divide $n^n$, whose only prime factors are those of $n$. So the division never comes out even, and the shuffle is biased for every deck of three or more cards.

For four cards the 256 runs fall on the 24 orders between 8 and 15 times each. The order 2143, two neighbouring pairs swapped, gets 15 runs and the most; the orders 4231 and 4123 get 8. A fair share would be 10⅔, which is the point: no arrangement of whole numbers can make it, however the program is adjusted, as long as each run has $n^n$ equally likely outcomes.

The fix is to change the count of runs. In the Fisher–Yates shuffle, as Richard Durstenfeld wrote it for computers in 1964 after Ronald Fisher and Frank Yates’s pencil-and-paper method of 1938, the card at position $i$ is swapped only with a card at position $i$ or later. The first step has $n$ choices, the next $n - 1$, and so on, giving exactly $n!$ equally likely runs, and a little checking shows each order comes from exactly one. Same loop, same random source, one bound changed — and the result is exactly uniform.

The bias grows with the deck #

For small decks the exact distribution over all orders can be computed by carrying the probability of every order through every step.

The spread widens quickly. For eight cards the most likely order is 4.64 times as likely as it should be, the least likely 0.31 times, a ratio of fifteen to one. The least likely order is the same at every size: the last card moved to the top and every other card shifted down one place, which the naive shuffle can produce in only a few of its runs. The total variation distance from the uniform distribution — the largest difference in probability the shuffle can make to any event — grows from 0.056 for three cards to 0.124 for eight, so the shuffle gets worse, not better, with more cards.

The original, unshuffled order has a curious path. For three cards it is among the least likely orders, at 0.89 times fair; by eight cards it is 1.84 times fair and in the top three per cent. David Robbins and Ethan Bolker studied this shuffle in 1981, and Daniel Goldstein and David Moews later proved what the climb suggests: for decks large enough, the single most likely outcome of the naive shuffle is no shuffle at all — the deck exactly as it started. The small decks drawn here do not show that, and the figure’s eighth card is far short of where the theorem takes hold. It is a case where small decks give exactly the wrong impression of what large ones do.

One character turns a shuffle into a cycle maker #

Fisher–Yates swaps position $i$ with a position from $i$ to the end; the naive shuffle with a position from anywhere. A third variant swaps with a position strictly after $i$ — the loop’s lower bound written as $i + 1$ instead of $i$, perhaps the most common slip in writing the shuffle from memory.

The result is not a slightly biased shuffle but a different object. It has $(n - 1)!$ equally likely runs, and each produces an order consisting of a single cycle: card 1 goes where card 2 was, card 2 somewhere else, and so on round all $n$ cards before returning. For six cards it produces exactly the 120 single-cycle orders, each with chance 1/120, and never any of the other 600. Sandra Sattolo published it as an algorithm in 1986, deliberately, because a uniformly random single cycle is sometimes exactly what is wanted. As a shuffle it is a disaster: no card can ever end where it started, since a single cycle through every card moves every card, so the shuffle is always a derangement, the kind of order nobody gets their own hat counted as about 37 per cent of all orders. A player who knew the deck was dealt this way would know that the top card is never the card that was on top.

The naive shuffle, by comparison, leaves single cycles at their fair 16.7 per cent and tilts towards exactly two cycles, 43.5 per cent against the fair 38.1, at the expense of three or more, so that its orders have fewer cycles on average than a fair shuffle’s. Each slip in the bounds of one loop leaves its own fingerprint on the cycle structure, and the cycle count is one of the first statistics a test of a shuffle would look at — the same kind of check the test that ranks the generators applied to the numbers themselves.

Sorting by a coin toss #

Another tempting shortcut is to shuffle by sorting with a comparison that answers at random: ask the sort routine to order the cards, and when it asks whether one card comes before another, toss a coin. If the sort were blind to the answers, this would give a random order. It is not blind, and different sort methods ask different questions.

With insertion sort, each new item is compared with the one before it and moves left only while the coin says so, so each extra step left costs another coin toss. The last item inserted stays in the last place half the time, and reaches the first place one time in sixteen. The first two items end in the first two places 31 per cent of the time each. A different sort method — merge sort, quicksort — would produce a different distortion, so the result of “sorting by a random comparison” depends on implementation details of a library routine that its user never sees. A ballot screen for choosing a web browser, shown to European users of one operating system in 2010, was found to order its choices this way and to favour some positions measurably; the fix was a proper shuffle.

How many shuffles give it away #

A bias of this size is not subtle, and it does not take much play to find. The chance that a particular card lands in a particular place is $1/52$, about 0.019, in a fair shuffle and a third more than that in the worst cells of the naive one. Over $N$ shuffles the count in one cell has a standard deviation of about $\sqrt{N/52}$, so an excess of a third of $N/52$ stands out by four standard deviations once $N$ is about $16 \times 52 / (1/3)^2$, roughly seven and a half thousand shuffles — a few evenings of an online card room. Looking at all 2,704 cells together, or at the specific cells the mechanism predicts, finds it faster still.

The divisibility argument says more than that the bias exists; it says no amount of tuning removes it while each step chooses among all $n$ positions. Replacing the random source by a better one, running more passes, or reseeding between deals all leave the count of runs a power of $n$, and all leave some orders more likely than others. The bias shrinks if the naive pass is repeated many times, because the repeated passes are a Markov chain that does converge to uniform; but a single pass of the correct algorithm is already exactly uniform, so there is never a reason to pay for the repetitions.

Why a perfect source is not enough #

All of these failures share one cause: a program’s random choices are counted in runs, and the runs are mapped onto outcomes by the program’s logic. Uniform runs give uniform outcomes only if every outcome receives the same number of runs. Fisher–Yates arranges that exactly; the naive shuffle cannot, for the divisibility reason; Sattolo’s arranges it for a different set of outcomes; and a random-comparator sort leaves it to the sort routine.

The same principle governs the step before shuffling, turning random bits into a random position. A generator produces bits, and a choice among 52 positions needs a uniform number from 0 to 51. Taking 6 random bits gives 64 equally likely values, and 64 is not a multiple of 52, so reducing them modulo 52 favours the first twelve positions. The repair is the same move fair bits from an unfair coin made with a biased coin: throw away the outcomes that cannot be shared evenly, and try again. Rejection costs a little randomness and buys exactness, and every correct shuffle routine does it, usually without its users knowing.

Finally there is the size of the source. A deck of 52 cards has $52! \approx 8 \times 10^{67}$ orders. A generator whose state is 32 bits can produce at most about four billion different decks, whatever shuffle it drives, and most decks are therefore impossible. A widely reported analysis of an online poker site in 1999 found both faults at once — a shuffle of the naive kind and a generator seeded from the time of day — which together let an observer who saw a few cards reconstruct the whole deck. As randomness that has to be earned put it for generators in general, the randomness of the output can be no greater than the randomness that went in.

What the pictures cannot show #

The distributions are exact for the decks drawn — the 52-card map follows each card exactly, and the orders of up to eight cards are carried exactly through every step — but they are exact for those sizes only. The claims about large decks, that the original order eventually becomes the single most likely one, are the theorem’s, not the figure’s; the figure shows the climb and not its end. The insertion-sort example is one sort method on five items; other methods distort differently, and none of them has been drawn.

Nor do the figures show the counting argument that makes Fisher–Yates exactly fair, or the one that makes Sattolo’s produce only single cycles. Both are short — each run builds a unique order, step by step, and in Sattolo’s case each step joins the next card into one growing cycle — and both are statements about every deck, not checks on a few.

Still open: whether any generator is good enough #

Every shuffle on this page assumed a perfect source of random numbers. Real programs use a pseudorandom generator, a deterministic rule that stretches a short seed into a long stream, and a correct Fisher–Yates shuffle driven by it is exactly as good as the stream. The question that matters is then whether the stream can be told apart from true randomness by any test that can actually be run.

Does any pseudorandom generator exist whose output no efficient test can distinguish from random? For particular generators, many tests have been passed and some have been failed, as the essays before this one found. For the general question the answer is unknown: such generators exist if and only if one-way functions exist — functions easy to compute and hard to invert — and whether one-way functions exist is unproved, and would itself imply that P differs from NP. So the honest status of every shuffle ever run on a computer is that it is fair if an unproved conjecture is true and the generator is one of the good ones. Two random shuffles reach every shuffle showed how little randomness it takes to reach every order; how little it takes to make every order equally likely, against every observer who might check, is the open half of the subject.