Modulo bias, in full
Start small. Take a generator returning integers 0 to 9, each with probability 1/10, and reduce it with x % 3 to land in 0 to 2. Residue 0 comes from inputs 0, 3, 6 and 9, which is four of the ten. Residue 1 comes from 1, 4 and 7, residue 2 from 2, 5 and 8, three inputs each. So 0 arrives 40 percent of the time and the other two arrive 30 percent each. The skew exists because 10 is not a multiple of 3.
The same thing happens at 32 bits, only faintly. 2^32 = 4,294,967,296 divides exactly by any power of two, so a coin flip, a d4 or a d8 built this way has no bias at all. It does not divide by 6. A naive d6 written as 1 + (x % 6) over the whole 32-bit range would leave faces 1 through 4 backed by 715,827,883 input values each and faces 5 and 6 backed by 715,827,882.
That 32-bit version is far too small to spot at a table, roughly one part in 716 million, but it is a genuine defect and it is cheap to remove. Rejection sampling handles it: discard the short tail so the surviving range is an exact multiple of the target, then every outcome sits on the same number of inputs. NIST sets out both routes, and marks the discard method as the one that produces no skew. The dice, coin and range tools here use it, which is why they can claim a flat distribution rather than a nearly flat one.
- Probability
- Modulo skew, Remainder bias
A worked example
A generator returning 0 to 9 uniformly, reduced by x % 3 and mapped to faces 1, 2, 3. Inputs 0, 3, 6, 9 give face 1. Inputs 1, 4, 7 give face 2. Inputs 2, 5, 8 give face 3. Over 10,000 rolls expect about 4,000 ones against 3,000 twos and 3,000 threes. Reject the input 9 first and nine inputs survive, three per face, so the counts flatten to about 3,333 each.
Sources
NIST describes two ways of turning random bits into a number in a range: the simple discard method, which it states produces a random number with no skew, and the simple modular method, which it states produces a value with a negligible but non-zero skew.
NIST SP 800-90A Rev. 1, Appendix A.5 — Converting Random Bits into a Random Number
See also
Where it comes up on this site
Modulo bias: frequently asked
It depends entirely on the ratio between the two ranges. Squeezing ten inputs down to three outcomes gives 40 percent against 30 and 30, which is enormous and would be obvious in a few hundred rolls. Squeezing a full 32-bit value down to six gives an excess of roughly one part in 716 million, which no amount of play at a table would ever reveal. Both are the same defect. Only one of them matters in practice, and both are removed the same way.
The low ones. Leftover values at the top of the source range land on the smallest remainders, so those outcomes pick up one extra input each.
No. They reject the leftover values rather than taking a plain remainder.