THE FOLD / CHEAT / THE BACKDOOR / THE LOADED-DICE TABLE
THE LOADED-DICE TABLE
a die loaded in constant time
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Walker’s alias method is the constant-time loaded die. To sample from an arbitrary discrete distribution p₁…pₙ, the naive way walks a cumulative table (O(n)) or bisects it (O(log n)). Alias sampling spends a little setup to build two arrays — a probability table and an alias table — that repack the distribution into n equal columns, each holding at most two outcomes. A draw is then: pick a column uniformly, flip one biased coin, take the column’s own outcome or its alias. One uniform, one comparison — O(1) forever, no matter how lopsided the distribution. Alastair Walker found it in 1974; Michael Vose gave the clean linear-time construction.
LIT verified live: the finished table reconstructs the input probabilities exactly (mass audit to 1e-12), and a million draws land within 0.0007 of every target probability (window.__aliasmethod). FIG no framing; the construction, the mass audit, and the empirical draws all run independently in-browser.
LIT verified live: the finished table reconstructs the input probabilities exactly (mass audit to 1e-12), and a million draws land within 0.0007 of every target probability (window.__aliasmethod). FIG no framing; the construction, the mass audit, and the empirical draws all run independently in-browser.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-backdoor — the cheat: a secret side-table that lets you into any distribution in constant time, bypassing the cumulative search entirely. AVAN (AI) built the instrument: the Vose construction, the exact mass audit, and the million-draw check.
Credit as content: Alastair J. Walker (1974–77); Michael Vose (1991, the linear-time build); idea-bank vein E, ‘THE LOADED-DICE TABLE’. The weave: David names the backdoor; I confirm each column holds two outcomes and the masses balance exactly.
Credit as content: Alastair J. Walker (1974–77); Michael Vose (1991, the linear-time build); idea-bank vein E, ‘THE LOADED-DICE TABLE’. The weave: David names the backdoor; I confirm each column holds two outcomes and the masses balance exactly.
3 ONE DIMENSION
The distribution repacked: n equal columns, each split between its own outcome and one alias.
4 TWO DIMENSIONS · INTERACTIVE
Roll the loaded die in bulk; the frequencies converge onto the target bars.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the equal columns any distribution flattens into.
AVAN’s addition (the inverse-companion): don’t search the distribution — reshape it. The inverse of ‘find where u falls in the cumulative’ is ‘pre-slice the mass into n fair columns of two tenants each’. Magenta are the alias hand-offs between columns; green is the flat table one coin-flip deep. A crooked die made honest by carpentry.
LIT Genuine Walker/Vose alias method (Alastair J. Walker 1974–77; Michael Vose 1991; idea-bank vein E, 'THE LOADED-DICE TABLE'). Verified live: the table reconstructs the input probabilities exactly (mass audit to 1e-12), and 10⁶ draws land within 0.0007 of every target probability (window.__aliasmethod.ok).
FIG No framing; the construction, the mass audit, and the empirical draws all run independently in-browser. The AVAN inverse is honest — instead of searching the distribution, reshape it: the inverse of 'find where u falls in the cumulative' is 'pre-slice the mass into n fair columns of two tenants each'. Magenta are the alias hand-offs between columns; green is the flat table one coin-flip deep. A crooked die made honest by carpentry.
FIG No framing; the construction, the mass audit, and the empirical draws all run independently in-browser. The AVAN inverse is honest — instead of searching the distribution, reshape it: the inverse of 'find where u falls in the cumulative' is 'pre-slice the mass into n fair columns of two tenants each'. Magenta are the alias hand-offs between columns; green is the flat table one coin-flip deep. A crooked die made honest by carpentry.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE BACKDOOR · David Lee Wise (ROOT0), with AVAN