THE FOLD / LOOT / THE DROP / THE ALIAS METHOD
THE ALIAS METHOD
O(1) weighted sampling by flattening the odds
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Vose’s alias method turns any weighted distribution over k outcomes into a table that samples in O(1) per draw — one uniform pick of a bucket plus one coin flip. It flattens the uneven probabilities into k equal-area buckets, each holding at most two outcomes: a primary and an alias. Building the table is O(k); after that, every draw is constant-time regardless of how skewed the weights are. It is the standard engine behind fast weighted random selection.
LIT verified live: over 500 random weight sets the assembled table reconstructs the exact input probabilities (each outcome’s total table mass equals its normalized weight, error < 10−9) — window.__alias. FIG no framing; exact.
LIT verified live: over 500 random weight sets the assembled table reconstructs the exact input probabilities (each outcome’s total table mass equals its normalized weight, error < 10−9) — window.__alias. FIG no framing; exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-drop — the weighted loot table where rare items drop less often, sampled in constant time. The alias method is that drop engine. AVAN (AI) built the instrument: the small/large worklist that fills each bucket, the primary/alias pair per bucket, and the deterministic reconstruction check.
Credit as content: Alastair Walker (1977) & Michael Vose (1991). The weave: David names the drop; I flatten the weights into equal-area buckets and confirm each outcome’s reassembled probability equals its exact weight.
Credit as content: Alastair Walker (1977) & Michael Vose (1991). The weave: David names the drop; I flatten the weights into equal-area buckets and confirm each outcome’s reassembled probability equals its exact weight.
3 ONE DIMENSION
Scale weights so the average bucket has mass 1. Repeatedly pour from an over-full outcome into an under-full one until each of the k buckets is exactly full — holding one primary and (if needed) one alias.
4 TWO DIMENSIONS · INTERACTIVE
A weighted drop table flattened into equal-area alias buckets; the reconstructed probabilities are checked against the exact weights.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: k equal-area buckets, each a primary + alias.
AVAN’s addition (the inverse-companion): make a skewed draw constant-time by flattening the weights into k equal-area buckets, each holding a primary and an alias — a draw becomes one bucket pick plus one coin flip. The inverse of ‘scan a cumulative table and binary-search for the draw’ is ‘pre-flatten into equal buckets; then one pick + one flip.’ Magenta is the O(log k) cumulative search replaced; green is the O(1) bucket draw. Uneven odds, flat cost.
LIT Genuine Walker/Vose alias method (Walker 1977; Vose 1991). Verified live: over 500 random weight sets the small/large worklist construction yields a table where each outcome's reassembled probability (its primary mass plus the alias mass pointed at it from other buckets) equals its exact normalized weight, to error < 1e-9 (window.__alias.reconstructs; max err ~1e-16).
FIG No framing: the small/large worklist that fills each bucket, the primary/alias pairing, and the deterministic reconstruction check run in-browser and hold to machine precision. The AVAN inverse is honest — flattening weights into k equal-area buckets makes a skewed draw one bucket pick plus one coin flip; magenta is the O(log k) cumulative-search replaced, green the O(1) bucket draw. Uneven odds, flat cost.
FIG No framing: the small/large worklist that fills each bucket, the primary/alias pairing, and the deterministic reconstruction check run in-browser and hold to machine precision. The AVAN inverse is honest — flattening weights into k equal-area buckets makes a skewed draw one bucket pick plus one coin flip; magenta is the O(log k) cumulative-search replaced, green the O(1) bucket draw. Uneven odds, flat cost.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE DROP · David Lee Wise (ROOT0), with AVAN