A seed is a deck

A perfect coin and a biased shuffle found two ways to deal a biased deck from a perfect source of randomness: swap each card with any card instead of a card not yet placed, and the $n^n$ equally likely runs cannot divide evenly among $n!$ orders. Fisher and Yates’s shuffle repairs that exactly. That essay then noted, in one paragraph, a second fault that no repair to the shuffle can touch: the source is never perfect, and a program’s random numbers come from a generator with a finite state.

This essay makes that paragraph the argument. A correct shuffle driven by a pseudorandom generator is a function. Its input is the generator’s starting state, the seed; its output is an ordering of the deck. Everything about the deal — which orders can occur, how often, what an observer can infer — is a property of that function, and on small enough cases the function can be computed for every input.

Nine cards and sixty-five thousand seeds #

Take the linear congruential generator $x \mapsto 25173x + 13849 \pmod{2^{16}}$, a classic 16-bit rule with the longest possible period, and let it drive a Fisher–Yates shuffle of nine cards: at each step, the next output, scaled into range, picks which of the remaining cards goes into the next place. Nine cards need eight random choices, and the deal is completely determined by the starting state. There are 65,536 starting states and 362,880 orders of nine cards, so before computing anything the pigeonhole principle says that at least 297,344 orders can never be dealt.

The computation runs every seed. It finds that 62,616 orders are dealt, 17.3% of them, and 300,264 never are. In the figure’s small window — the 5,040 orders that begin with cards 0 and 1 — 859 squares are lit, and the rest are orders that no run of the program, ever, on any machine, will produce. The shuffle is correct; the generator has a full period and passes simple statistical tests; and five orders in six are impossible.

Most of the dealt orders come up from exactly one seed. 2,895 come up from two, eleven from three, and one from four. That is about what assigning seeds to orders at random would produce — the birthday problem with 65,536 people and 362,880 birthdays predicts 59,959 distinct orders and a few thousand shared ones — and the generator does a little better than random, spreading its seeds with slightly fewer coincidences than chance would. The reason is the same regularity that makes the generator weak elsewhere. Successive outputs of a linear congruential generator lie on a small number of planes, so neighbouring seeds produce systematically different runs rather than independent ones, and runs that differ systematically collide less often than independent ones would. A structure that would ruin a simulation sampling points in space happens, here, to spread the deals more evenly — a reminder that a generator is good or bad only relative to the use it is put to, and that a test passed for one use says little about another.

Why a correct shuffle cannot help #

It is tempting to think a cleverer shuffle could stretch a small seed further — shuffle twice, or shuffle and then cut, or mix in the time between keystrokes. None of it helps against the count, and it is worth seeing why each fails. Shuffling twice with the same pseudorandom generator continues the same deterministic run, so the output is still a function of the seed: the same 65,536 starting points, mapped to at most 65,536 decks by a longer function. Cutting the deck afterwards at a position chosen by the same pseudorandom generator is again a function of the seed. Only fresh randomness from outside the generator — a new seed — adds decks to the repertoire, and it adds exactly as many bits as it contains.

The deeper statement is that no deterministic procedure, however intricate, can increase the number of distinct outputs beyond the number of distinct inputs. Information-theoretically, a seed of $b$ bits is a choice among $2^b$ possibilities, and a deck of 52 cards drawn uniformly is a choice among $2^{225.58}$; the gap of 194 bits cannot be manufactured by computation. What computation can do is hide the gap — make the $2^{b}$ reachable decks impossible to tell apart from the rest without knowing which they are — and that is the whole of what a cryptographic generator promises.

Which bits are read matters #

There are two common ways to turn a generator’s output into a random position from 0 to $i$: scale it, $\lfloor x(i + 1)/2^{16} \rfloor$, which reads the high bits, or take a remainder, $x \bmod (i + 1)$, which reads the low bits. For a perfect source they are equivalent, apart from a small rounding bias. For a linear congruential generator modulo a power of two they are nothing alike. The lowest bit of its output simply alternates, the lowest two bits cycle with period four, and in general the lowest $k$ bits repeat every $2^k$ steps. A remainder by a small number reads mostly those bits.

Driven by the low bits, the same 65,536 seeds produce only 22,282 orders — barely a third of what the high bits reach — and the orders they do produce are piled up: 7,233 of them are dealt by three seeds each, two by eight. The shuffle has the same code and the same pseudorandom generator; only the way of reading the output has changed.

Where each card lands #

The damage shows in the simplest statistic a player could track. With the high bits, every card lands in every position within 2.4% of the one-in-nine a perfect shuffle would give. With the low bits, some placements happen 132% more often than they should and others hardly at all. The pattern is periodic in position, reflecting the short cycles of the low bits: a card’s final place depends on remainders by $9, 8, 7, \ldots$ of outputs whose last bits march in step.

It is worth being precise about what the bias is not. It is not the modulo bias of reducing a 16-bit number by a remainder — 65,536 is not a multiple of 9 or 7, so a few residues are favoured by one part in seven thousand, far too little to show here. The 132% comes from the dependence between successive low bits: the remainders by 9, 8 and 7 of three consecutive outputs are not independent, because their last few binary digits are not, and the shuffle multiplies those dependences along its eight steps.

That bias is invisible to the first tests anyone applies to a generator. The output sequence, read whole, looks uniform; its successive values are not obviously correlated; it has the full period. The spectral test would condemn this pseudorandom generator’s low bits immediately, and so would a test aimed at the shuffle, but a program that merely checks its random numbers look random would pass.

How many cards give the seed away #

The pigeonhole limit is a statement about which decks can occur. The more dangerous property is the converse: since each seed deals one deck, the deck reveals the seed, and the seed reveals the deck.

Shuffle a full deck from each of $2^{20}$ seeds of a 24-bit generator — about a million deals — and ask, for each seed, whether any other seed deals the same first $k$ cards. With three cards seen, almost every seed is ambiguous: there are 132,600 possible ordered triples and a million seeds sharing them. With four cards, 8% of seeds are already unique; with five, 69%; with six, every one. Seeing six cards of a deal identifies the seed, and from the seed every remaining card can be computed.

A 32-bit seed needs only one card more, since $52 \times 51 \times 50 \times 49 \times 48 \times 47 \times 46$ exceeds $2^{32}$ by a factor of about 160. That is not a thought experiment. In 1999 a security team showed that an online poker site seeded its shuffle from the number of milliseconds since midnight — about $2^{26}$ possible seeds — and that a player who saw their own two cards and the first three community cards could identify the seed in real time and know every other player’s hand. The shuffle algorithm was also the naive one of the previous essay, but the seed alone was enough. It is the same weakness, at a larger scale, as four outputs of a generator giving away its rule: a generator’s outputs are a function of a small secret, and a function of a small secret can be inverted by trying every secret.

How many bits a deck needs #

Every order of $n$ cards can be dealt only if the generator has at least $n!$ states, so its state needs at least $\log_2 n!$ bits. That number grows a little faster than $n \log_2 n$: a 32-bit seed is enough for twelve cards, a 64-bit seed for twenty, a 128-bit state for thirty-four. A full deck needs 225.58 bits. Most generators in common use before the 1990s had 32 or 48 bits of state; many standard-library generators today have 64.

The Mersenne twister, with nineteen thousand bits of state, clears the bar for 2,080 cards. That is why it is often recommended for shuffling, and the recommendation is half right. Having enough states is necessary for a fair deal and not sufficient: the twister’s output is linear over the field of two elements, so its state can be recovered from 624 consecutive outputs, after which every future deal is known. Fairness against an observer needs a generator whose outputs cannot be used to predict the next — a cryptographic one — and enough state; the counting in these figures settles only the second.

The share of decks a seed can reach #

For a full deck the arithmetic is stark. A 16-bit generator can deal at most one deck in $10^{63}$; a 32-bit one, one in $10^{58}$; a 64-bit one, one in $10^{49}$; even a 128-bit state reaches only one in $10^{29}$. A bridge club running a 32-bit generator could deal a hand every second for the age of the universe and use a vanishing fraction of its program’s repertoire, which is itself a vanishing fraction of the decks that exist. None of this shows in any single deal. Each hand from the 32-bit program looks exactly like a random hand; the defect is in the set of hands, not in any member of it.

Games that care only about part of the order need fewer bits, and the counting says exactly how many. A bridge deal is a division of the deck into four hands of thirteen with the order inside each hand irrelevant, and there are $52!/(13!)^4 \approx 5.4 \times 10^{28}$ of them — about $2^{95.4}$. A 64-bit generator can deal one bridge deal in about $10^{10}$, a 32-bit one one in $10^{19}$. A single five-card poker hand is one of only 2,598,960 sets, which a 32-bit seed covers many times over; what it cannot cover is the deal as a whole, the hands of every player at the table together, and that is what an opponent who identifies the seed learns.

There is a sense in which this does not matter and a sense in which it matters completely. For a card game against friends, a deck chosen uniformly from $2^{32}$ possibilities is as good as one chosen from all $52!$, because nobody can tell which set it came from. For any setting where someone could benefit from knowing the deal — gambling for money, a cryptographic protocol that shuffles, a lottery — the small state is a complete break, because the reachable decks can be listed.

Seeds in the wild #

The same arithmetic governs every place a program draws a seed. A seed taken from the clock has as many values as the clock has readings in the plausible window — the milliseconds since midnight, or the seconds since the program’s author could have started it — which is often well under $2^{32}$. A seed taken from a process number has fewer still. A seed typed by a user is a password, with all of a password’s poverty. Each of these can be tried exhaustively, and each, combined with a few observed outputs, gives away everything the generator will ever produce.

That is why modern systems seed from the operating system’s pool of entropy, gathered from hardware events, and use generators whose state is refreshed from that pool. It is also why a generator’s period, the number printed in its documentation, is a poor guide to what it can deal. The period of a linear recurrence measures how long its sequence runs before repeating, and a generator with a period of $2^{19937} - 1$ seeded with 32 bits can still reach only $2^{32}$ of its starting points: the period is about the length of the road, and the seed is about how many places it can be joined.

What the computations show and assume #

Every count for nine cards is exact: every seed was run, every deal ranked, and the counts and placements tallied. Ranking an order means giving it its position in dictionary order among all 362,880, computed from how many smaller cards follow each card — a numbering that turns the set of dealt orders into a set of whole numbers that can be marked off one by one, which is how the hero’s window and the count of 62,616 were produced. The 52-card identification figure is exact for the $2^{20}$ seeds it uses; its 32-bit curve is the expectation for independent deals, and a real generator’s deals are not independent — the high-bit 16-bit example shows that structure can help, and the low-bit one that it can hurt. Neither generator is one anybody should use; they were chosen because every one of their states can be examined, and their faults are scaled-down versions of faults that afflict the larger generators that cannot be.

The figures assume a correct Fisher–Yates shuffle throughout. Every bias and every limit here belongs to the generator and to how its output is read, and all of them survive a shuffle that is itself beyond reproach.

Still open: what a generator must have #

What property of a generator guarantees that a shuffle driven by it is indistinguishable from a perfect one? For an adversary with unlimited computing power, nothing short of $\log_2 n!$ bits of true randomness will do, by the counting above. For an adversary limited to feasible computation, a cryptographically secure generator with a long enough seed is believed to suffice — but “believed” is the operative word, since the existence of such generators is equivalent to the existence of one-way functions, which would imply that P is not NP and has not been proved. Between those two poles lies the everyday question of which statistical tests a non-cryptographic generator must pass for shuffles used in simulation to give correct answers, and no finite list of tests is known to be enough: a generator can pass every test in a standard battery and still fail a test designed around the particular simulation it drives.

A function of a small secret #

A shuffle driven by a pseudorandom generator deals exactly the decks its seeds map to, and no others. With a 16-bit generator and nine cards the map reaches 62,616 of 362,880 orders from the high bits and 22,282 from the low, whose short cycles also put cards in some positions more than twice as often as they should. On a full deck a 32-bit seed reaches one deck in $10^{58}$, the first six or seven cards dealt identify the seed and everything after it, and a fair deal needs at least 226 bits of state — necessary, and, against anyone who can watch, not sufficient.