THE FOLD / LOOT / THE MINT / THE MODULAR BIAS
THE MODULAR BIAS
you cannot partition a set into equal parts that do not exist
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Take a uniform random number in
LIT verified live and computed exactly, not sampled. Over
[0, R) and reduce it modulo k. Unless k divides R exactly, some residues get one extra chance and the result is not uniform.LIT verified live and computed exactly, not sampled. Over
R = 232: with k = 6 there are 715,827,882 complete cycles and 4 favoured residues, an excess of 0.00000014% — harmless. With k = 1,000,000,007 there are only 4 complete cycles and the excess is 25%. With k = 3,000,000,000 there is 1 cycle and the excess is 100%: some outcomes are twice as likely as others.2 HOW IT WAS WEAVED · AI + HUMAN
Modulo bias is why every good library uses rejection sampling rather than
AVAN (AI) had the relationship backwards at first. I gated on a large divisor giving negligible bias, which is the intuition and is wrong: a large k leaves fewer complete cycles in the range, so the bias grows with
rand() % n.AVAN (AI) had the relationship backwards at first. I gated on a large divisor giving negligible bias, which is the intuition and is wrong: a large k leaves fewer complete cycles in the range, so the bias grows with
k/R. Correcting it produced the better instrument — the sweep from 715,827,882 cycles down to 1 is the whole mechanism, visible in a single column.3 ONE DIMENSION
Divisor against excess probability. Exact, not sampled.
4 TWO DIMENSIONS · INTERACTIVE
Grow the divisor until the bias is unmissable.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a range that does not divide evenly.
AVAN’s addition (the inverse-companion): the forward reading is that modulo introduces bias into a uniform source. The inverse is that the source was never uniform over the thing you wanted. It was uniform over
232 outcomes, and you asked for k; unless k divides that, no function of one draw can be uniform, because you cannot partition a set into equal parts that do not exist. Read backwards, rejection sampling is not a correction — it is the admission that sometimes you must throw the draw away and ask again, because there is no arithmetic that makes the counts come out even.LIT computed exactly rather than sampled over R = 2^32: k = 6 leaves 715,827,882 complete cycles and 4 favoured residues for an excess of 0.00000014%, k = 1,000,000,007 leaves only 4 cycles and an excess of 25%, and k = 3,000,000,000 leaves 1 cycle and an excess of 100% - some outcomes twice as likely as others
FIG Modulo bias is why every good library uses rejection sampling rather than rand() % n. AVAN had the relationship backwards at first: I gated on a large divisor giving negligible bias, which is the intuition and is wrong, because a large k leaves fewer complete cycles in the range so the bias grows with k/R. Correcting it produced the better instrument - the sweep from 715,827,882 cycles down to 1 is the whole mechanism in a single column.
FIG Modulo bias is why every good library uses rejection sampling rather than rand() % n. AVAN had the relationship backwards at first: I gated on a large divisor giving negligible bias, which is the intuition and is wrong, because a large k leaves fewer complete cycles in the range so the bias grows with k/R. Correcting it produced the better instrument - the sweep from 715,827,882 cycles down to 1 is the whole mechanism in a single column.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE MINT · David Lee Wise (ROOT0), with AVAN