Fair shuffling and modulo bias

A random number generator produces bits: bytes from 0 to 255, or 32-bit blocks from 0 to 4,294,967,295. Almost nothing anyone wants is in that form. A die needs 1 to 6, a raffle 1 to 250, a shuffled deck one of 52! orders. The step from raw bits to the thing you want is where most unfair randomness comes from, and the errors are invisible in a handful of results.

Why the remainder is biased

The shortest way to turn a random value into a number from 1 to n is to divide by n, keep the remainder and add 1. It is fair only when n divides the number of possible raw values exactly. Otherwise the raw values can’t be shared out evenly, and the leftovers all land on the smallest numbers.

A byte shows it clearly. A byte has 256 values, and 256 = 2 × 100 + 56. Mapped to 1 to 100 by remainder, the numbers 1 to 56 can each be reached from three bytes (1 from bytes 0, 100 and 200), and 57 to 100 from only two.

In the first row the low numbers are 1.5 times as likely as the high ones. The bias shrinks as the raw values get larger, but it only disappears when the range divides them exactly, which for a power of two means a range that is itself a power of two.

Rejection sampling

The fix is to throw away the leftovers. For 1 to 100 from bytes, accept only bytes 0 to 199, which divide evenly into 100 groups of two, and draw a fresh byte whenever the byte is 200 or more. Every number then has exactly 2 chances in 200. The cost is a redraw 56 times in 256 (21.9%), or 1.28 bytes per number on average.

With larger raw values the cost almost vanishes. Using 32-bit blocks for a range of 100, only the top 96 of the 4,294,967,296 possible values are rejected, a redraw about once in 44.7 million draws. This is the method used by the random number generator and every other tool on this site.

The Fisher–Yates shuffle

Shuffling has the same problem in a different form. A fair shuffle must make all n! orders equally likely: 6 for three items, 3,628,800 for ten, about 8.07 × 10⁶⁷ for a deck of 52.

The standard method takes its name from the statisticians Ronald Fisher and Frank Yates, who described a pencil-and-paper version. The computer form was published by Richard Durstenfeld in 1964 as Algorithm 235 in Communications of the ACM, and Donald Knuth gives it as Algorithm P in section 3.4.2 of The Art of Computer Programming. It works from the end of the list:

1. Pick a uniformly random position from the first to the last, inclusive, and swap that item into the last place.
2. Leave the last place alone and repeat with the list one shorter.
3. Stop when one item is left.

With n items, the first step has n choices, the next n − 1, and so on down to 1, giving n! equally likely sequences of choices. Each sequence produces a different order, so every order has exactly one way to happen. The list randomizer and random card generator shuffle this way.

The swap-with-anything mistake

A natural-looking variant visits each position in turn and swaps it with any position in the list, not just one from the part still to be shuffled. It does the same amount of work and looks just as random, but it isn’t fair. With 3 items it makes 3 × 3 × 3 = 27 equally likely sequences of swaps, and 27 can’t be divided evenly among 6 orders.

The imbalance grows with the list. With 4 items there are 256 sequences for 24 orders, and the most likely order comes up 15 times to the least likely’s 8; with 7 items it is 543 to 64. It can never come out even for 3 or more items: n − 1 divides n! but shares no factor with nⁿ.

Sorting with a random comparator

Another common shortcut sorts the list with a comparison that answers at random, such as list.sort(() => Math.random() - 0.5) in JavaScript. A sorting algorithm assumes its comparisons are consistent, and the ECMAScript standard says that when they are not, the resulting order is implementation-defined. In practice it is biased in a way that depends on the browser’s sorting algorithm.

Counting shows why it can’t be fair. Each comparison is a coin flip, so every outcome has a probability that is some whole number divided by a power of 2, and 1/6 is not such a number. A simple insertion sort of three items, with each comparison 50/50, leaves ABC and BAC with a 1 in 4 chance each and the other four orders with 1 in 8. A merge sort gives a different but equally uneven split.

The 1999 online poker shuffle

The best-documented case of these mistakes costing money was found in 1999 by a team at Reliable Software Technologies, who published the details as “How We Learned to Cheat at Online Poker”. The shuffle in the Texas Hold’em software behind the PlanetPoker card room had three faults:

• it used the swap-with-anything loop above, so some deck orders were more likely than others;
• an off-by-one error chose swap positions from 1 to 51 only, so the 52nd card never ended up in the 52nd place;
• the random generator was seeded with the number of milliseconds since midnight, giving only 86,400,000 possible seeds.

A deck has about 8.07 × 10⁶⁷ orders, roughly 2²²⁶. A generator with a 32-bit seed can reach at most 4,294,967,296 of them, and this one reached at most 86.4 million. By synchronising with the server’s clock, the team cut the candidates to about 200,000, few enough to search in real time. After seeing their own two cards and the three cards of the flop, their program could work out every other card in the deck.

The lesson goes beyond the shuffle: a correct algorithm can only be as unpredictable as its seed.

What this site does

All tools on this site share one small module, rng.ts, which reads random 32-bit blocks from the browser’s crypto.getRandomValues(), the cryptographic generator described in the guide to true and pseudo-random numbers.

There is no seed to guess and no remainder bias, and each step of a shuffle picks its position with exactly equal chances, so no order of a list or a deck is favoured.