Shuffling Is Harder Than It Looks: A Million Runs of the One-Line Shuffle

A million shuffles of four items

Four items have twenty-four orderings. That is small enough to count exhaustively, which is what makes it the right test case: run a shuffle a million times, tally how often each of the twenty-four comes out, and a fair shuffle has to put roughly 41,667 in every bucket. Anything that systematically favours some orderings will show up as a lump, and one number — the chi-square statistic — turns the whole table into a single verdict. With 23 degrees of freedom, a fair method scores around 23, and anything above 27.32 would happen less than 5% of the time by chance alone.

The one-liner scored 125,397. Not 30, not 300 — five thousand times the threshold. The commonest ordering, BADC, came up 62,810 times; the rarest, DBCA, 30,998. The original order ABCD survived intact 62,485 times, half again as often as it should. Running the same million through a correctly written Fisher-Yates shuffle produced 10.3, which is what a fair method looks like: the extreme counts were 41,434 and 41,879, a spread of about 1%. Stretching the test to five items made the gap wider still — 229,683 against 89.0 — because every extra element gives the sort algorithm one more decision to make badly.

Not twenty-four probabilities — two

The counts are not scattered. Sorted, they fall into two tight clusters: eight orderings around 62,500 and sixteen around 31,250. Those are exactly 1/16 and 1/32 of a million, and the arithmetic closes — 8 × (1/16) + 16 × (1/32) = 1. Four million further runs tested that hypothesis directly and produced a chi-square of 19.7 on 23 degrees of freedom, which is a good fit. So the one-line shuffle on this engine is not approximately uniform with a wobble; it is a two-valued distribution in which half your probability mass is crammed into a third of the outcomes.

The eight favoured orderings share a property worth noticing: ABCD, ABDC, ADBC, BACD, BADC, BDAC, DABC and DBAC all keep C out of the first two positions. That is not mysticism, it is the sort algorithm leaking through. A four-element array is short, so V8 never leaves its binary-insertion path; the comparator gets called 4.5 times on average, and 4.5 coin flips cannot possibly generate 24 equally likely outcomes, because 24 does not divide any power of two. The bias is baked into the shape of the decision tree before randomness is even involved.

The bias belongs to the engine, not to the language

ECMA-262 requires the comparison function passed to sort to be a consistent comparator: it must be transitive, it must be antisymmetric, and it must give the same answer for the same pair every time. A comparator built on Math.random breaks all three within a single call. The specification's response is not to define what happens; it is to say that if the comparator is inconsistent, the result of the sort is implementation-defined. That single sentence is the whole story. You have not written a shuffle with unusual statistics — you have written a program whose output the standard declines to specify.

The practical consequence is that these counts are a measurement of one engine at one version, not a universal constant. V8 has changed its sort more than once; a run on a different engine, or on the same engine after an upgrade, will produce a different lumpy distribution, and an array long enough to trip the merge path will produce a different one again. Nothing in the standard forbids that, and nothing warns you when it happens. A shuffle whose statistical properties move when the runtime is patched is not a shuffle you can test.

Fisher-Yates, and the off-by-one that ruins it

The correct algorithm — Knuth's Algorithm P — walks the array from the last index down to the second, and at each position i draws a random index j uniformly from 0 to i inclusive, then swaps positions i and j. Three details carry the whole proof. The loop descends. The draw includes i itself, so an element is allowed to stay where it is. And the range shrinks by one each iteration, so the number of possible execution paths is n × (n−1) × … × 2 = n!, which is exactly the number of permutations. A bijection between execution paths and outcomes is what uniformity means, and it holds for every n, not just for the ones you tested.

Change one character and it breaks. The common variant walks the array upwards and draws j from the whole array each time, which feels more random and is not. That version has n^n execution paths, and n^n is never a multiple of n! for n above 2, so some permutations must be reachable in more ways than others. Measured on the same million runs it scored 29,913 — a thousand times the threshold, with the commonest ordering at 58,698 and the rarest at 31,233. It is the more dangerous of the two errors precisely because it looks like the textbook version and passes every eyeball test.

Modulo bias: the second way to bend a shuffle

Fisher-Yates needs a uniform integer in a range, and the obvious way to get one from a random 32-bit value is to take it modulo the range size. That is uniform only when the range divides 2^32 exactly. It usually does not: 2^32 mod 52 is 48, so 48 of the 52 outcomes receive one more preimage than the other four. At 32 bits the resulting excess is about a millionth of a percent and nobody will ever see it. Shrink the source to a single byte and the same arithmetic becomes brutal: 256 mod 52 is again 48, but now 48 outcomes get 5 preimages and 4 get only 4 — a 25% excess, visible in a few thousand draws.

The fix is rejection sampling and it costs almost nothing. Compute the largest multiple of the range that fits in your source — for a 32-bit draw and a range of 52 that is 2^32 minus 48 — draw again whenever the value lands above it, and take the modulo only of accepted values. The rejection region is 48 values out of 4,294,967,296, so the expected number of extra draws is about one in ninety million. You pay a comparison per call and buy exact uniformity, which is the best trade in this entire article.

Math.random is not a card shuffler

Even a perfect Fisher-Yates is limited by the generator underneath it. A 52-card deck has 52! orderings, which is 8.07 × 10^67, or about 2^225.6. The generator behind Math.random in V8 carries 128 bits of internal state, so it can reach at most 2^128 ≈ 3.4 × 10^38 deck orders — a fraction of 4.2 × 10^-30 of the total. The overwhelming majority of shuffles of a standard deck are simply not producible, no matter how many times you call it. That is a hard mathematical ceiling, not an implementation flaw, and it applies to every pseudorandom generator with less state than the space it is asked to cover.

Two further properties matter in practice. Math.random is not seedable and not reproducible: the specification gives no way to fix a starting point, and it explicitly requires distinct realms to produce distinct sequences, so a bug you saw once cannot be replayed. And it is not unpredictable in the cryptographic sense — an observer who sees enough outputs can reconstruct the state and predict the rest. If anyone could gain by guessing your shuffle — a raffle, a draw with a prize, a security token, anything shuffled before an audience — use crypto.getRandomValues instead, with rejection sampling on top. If the shuffle is a seating plan or a practice quiz, Math.random with a correct Fisher-Yates is entirely fine.

Frequently asked questions

Is sorting with a random comparator always biased, or only in some browsers?

Always biased, but biased differently everywhere. The standard requires a consistent comparator and declares the result implementation-defined when it does not get one, so each engine — and each version of each engine — produces its own lumpy distribution. On Node 26.3.0 the four-item case collapses to just two probabilities, 1/16 for eight orderings and 1/32 for the other sixteen, which a four-million-run test confirms with a chi-square of 19.7 on 23 degrees of freedom. Another engine will not give you those exact numbers; it will give you different wrong numbers. That is worse than a known, fixed bias, because there is nothing stable to test against and a runtime upgrade can change the statistics of your draw without changing a line of your code.

How do I write Fisher-Yates so that it is actually correct?

Start at the last index and walk down to index 1. At each position i, draw j uniformly from 0 to i inclusive, then swap the elements at i and j. Three things have to be right at once: the loop descends, the draw includes i itself, and the range shrinks by one every iteration. Get all three and the number of execution paths is exactly n factorial, one per permutation, which is what makes the output uniform for every array length rather than for the lengths you happened to test. The variant that walks upwards and draws j from the whole array each time is the classic error — it has n to the power n paths, which is never a multiple of n factorial above n = 2, and it measured a chi-square of 29,913 on the four-item test where a fair shuffle scores about 23.

Do I need crypto.getRandomValues, or is Math.random good enough?

The test is whether anyone could gain by predicting the outcome. Shuffling quiz questions, seating a classroom, randomising the order of practice problems: Math.random inside a correct Fisher-Yates is fine, and the difference will never show. Drawing a prize, picking an audit sample, generating anything that behaves like a token: use crypto.getRandomValues, because Math.random is a pseudorandom generator whose internal state can be reconstructed from a modest run of outputs, after which every future value is predictable. There is a second, quieter reason. A 52-card deck has about 2^225.6 orderings and V8's generator carries 128 bits of state, so it can reach at most one deck order in 10^30 of them. That ceiling is inherent to the state size, not to the quality of the algorithm.

What exactly is modulo bias, and when does it matter?

It is what happens when you squeeze a range that does not divide your source. Take a random 32-bit value and reduce it modulo 52 and you get a number from 0 to 51, but 2^32 divided by 52 leaves a remainder of 48, so 48 of those outcomes have one more source value mapping onto them than the remaining four. At 32 bits the resulting excess is around a millionth of a percent — genuinely negligible. The same arithmetic on an 8-bit source is a different animal: 256 modulo 52 is also 48, but now the favoured outcomes get 5 source values and the others only 4, a 25% excess that a few thousand draws will expose. The fix is rejection sampling: reject any draw at or above the largest multiple of the range that fits your source, which for 32 bits and a range of 52 rejects 48 values out of 4.29 billion, about one draw in ninety million.

How would I test my own shuffle without a statistics background?

Shrink the problem until you can count everything. Take an array of four items, shuffle it a million times, and keep a tally of how often each of the twenty-four orderings appears — a dictionary keyed on the joined string is enough. Then look at two numbers: the largest count divided by the smallest, and the count of the original unshuffled order. A fair shuffle gives a ratio near 1.01 at that sample size and leaves the original order at roughly 1 in 24. In the measurements here, Fisher-Yates gave 1.011 and the one-line sort gave 2.026, with the untouched order appearing 50% more often than it should. You do not need the chi-square to see that gap; the chi-square only tells you how impossible it is, and 125,397 against a threshold of 27.32 is about as impossible as measurements get.