Rejection sampling: the exact fix for modulo bias

In modulo bias we showed that folding a random byte onto the numbers 1–45 with the % operator makes low numbers 20% more likely — because 256 = 5 × 45 + 31, and those 31 leftover values have to land somewhere. This article is about the fix. It is almost insultingly simple, it is the method real cryptographic libraries use, and — this is the part worth internalising — it produces a distribution that is exactly uniform, not approximately.

The idea in one sentence

If the random value lands in the leftover zone, don't use it — throw it away and draw a fresh one.

The 8-bit example, continued

We want a number from 1 to 45 using random bytes (0–255). The largest multiple of 45 that fits in 256 values is:

5 × 45 = 225

So the rule is:

repeat:
    b = a fresh random byte          # 0..255
until b < 225                        # reject 225..255 (the 31 leftovers)
return (b % 45) + 1

Why this is exactly uniform: after rejection, b is a uniformly random value in 0–224 — 225 equally likely values, because our source was uniform and we merely conditioned on a subset; every survivor keeps equal weight. And 0–224 folds onto the 45 remainders perfectly evenly: each remainder 0–44 is hit by exactly 225/45 = 5 values. Every lottery number has probability exactly 5/225 = 1/45. Not 1/45 plus a small error term. Exactly 1/45, as a fraction of integers.

Compare the two mappings side by side:

"Doesn't the loop run forever?"

It can't be bounded in the worst case — that's the honest price of exactness — but the expected cost is tiny and the tail vanishes at blinding speed.

Each draw succeeds with probability p = 225/256 ≈ 87.9% and fails with probability 31/256 ≈ 12.1%. The number of draws until success follows a geometric distribution, whose mean is 1/p:

Expected draws per number = 256/225 ≈ 1.138

You can also see it as the series 1 + (31/256) + (31/256)² + … = 1/(1 − 31/256) = 256/225. About one extra draw per seven numbers generated.

The probability of needing more than k draws is (31/256)^k:

For a computer producing millions of bytes per second, this is a rounding error on a rounding error. And in production nobody uses 8-bit words anyway: with 32-bit words and a 45-number range, only 31 values out of 4,294,967,296 get rejected — one retry per ~139 million draws (the working is in how we built an unbiased generator).

Why "exactly, not approximately" is the whole point

There are approximate fixes floating around — for example scaling a random float (floor(random() * 45)) or using wider words to shrink the modulo skew. They all share the same defect: the bias gets smaller, but a bias remains, because no deterministic map from 2^k equally likely values onto 45 outcomes can be even when 45 doesn't divide 2^k. That's the pigeonhole principle and it is not negotiable.

Rejection sampling is different in kind, not degree. It changes the sample space: by discarding the leftovers, the space becomes a set whose size is a multiple of 45, and evenness becomes possible — then automatic. The output distribution is provably identical to a perfect 45-sided die. This is why it's the standard construction in serious libraries: OpenBSD's arc4random_uniform() is exactly this loop, documented as returning uniform values while "avoiding modulo bias", and NIST's digital signature standard FIPS 186-5 generates secret keys in a range by the same discard-and-retry pattern ("testing candidates") because key generation cannot tolerate any skew.

One subtlety worth naming: the trade is determinism for exactness. Plain modulo always finishes in one draw but is forever biased; rejection sampling is exactly fair but takes a random number of draws. Cryptographers and certifiers consistently choose the second — a fairness property you can prove beats a running time you can bound.

Where you can see it live

Our number generator runs precisely this construction — crypto.getRandomValues() for the raw words, rejection sampling for the range mapping, and a Fisher–Yates draw for lines without repeats. The full pipeline, with pseudocode you can check against the running page, is documented in how we built an unbiased generator. And if you want to verify rather than trust: feed any generator's output into our randomness tester and see whether the per-number frequencies behave — the biased and unbiased versions separate quickly, exactly as the table above predicts.