THE FOLD / LOOT / THE DROP / THE LOOT TABLE
THE LOOT TABLE
O(1) weighted sampling — Walker's alias method
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The alias method. A loot table has weights — common junk, rare epics. To roll a drop you could scan a cumulative list, O(n) per roll. Walker’s alias method (1974, cleaned up by Vose) does it in O(1), forever, after one O(n) setup.
The trick: pour n outcomes, each scaled so the average height is 1, into n columns. Some overflow (height>1), some fall short. Repeatedly take the excess off a tall column and pour it onto a short one until every column is exactly height 1 and holds at most two outcomes — a main one and an alias. To sample: pick a column uniformly, then flip a single biased coin between its main outcome and its alias. Two array lookups and one compare — constant time, any distribution.
LIT verified: this instrument builds the alias table for a set of weights, draws hundreds of thousands of samples, and the empirical frequencies match the target weights to within 1% (window.__alias.withinTol). FIG ‘loot drops’ is the wrapper; the leveling construction and the O(1) two-lookup sample are exactly Walker’s method.
The trick: pour n outcomes, each scaled so the average height is 1, into n columns. Some overflow (height>1), some fall short. Repeatedly take the excess off a tall column and pour it onto a short one until every column is exactly height 1 and holds at most two outcomes — a main one and an alias. To sample: pick a column uniformly, then flip a single biased coin between its main outcome and its alias. Two array lookups and one compare — constant time, any distribution.
LIT verified: this instrument builds the alias table for a set of weights, draws hundreds of thousands of samples, and the empirical frequencies match the target weights to within 1% (window.__alias.withinTol). FIG ‘loot drops’ is the wrapper; the leveling construction and the O(1) two-lookup sample are exactly Walker’s method.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this in THE DROP — the loot domain about what falls and how often. The alias method is quite literally how game loot tables sample weighted drops in constant time. AVAN (AI) built the instrument: the leveling of the columns, the biased-coin sample, and the convergence check.
The weave: David names the seat (the weighted drop); I make the leveling visible and the fairness measurable — the alias table in 1D, live sampling converging to the weights in 2D, the outcome dais with its overflow arrows in 3D. The sphere is the seam. Credit: A. J. Walker (1974), M. D. Vose (1991).
The weave: David names the seat (the weighted drop); I make the leveling visible and the fairness measurable — the alias table in 1D, live sampling converging to the weights in 2D, the outcome dais with its overflow arrows in 3D. The sphere is the seam. Credit: A. J. Walker (1974), M. D. Vose (1991).
3 ONE DIMENSION
The alias table: n columns, each leveled to height 1. The solid lower block is the column’s own outcome; the block above it is borrowed from its alias — the overflow of a richer outcome poured down to fill the gap. Every column holds at most two.
4 TWO DIMENSIONS · INTERACTIVE
Draw loot and watch the tally bars climb toward the target weights (the outlines). Every roll is one column pick + one coin flip — constant time no matter how many outcomes. Reweight reshuffles the table.
5 THREE DIMENSIONS + AVAN’S INVERSE
The outcomes on a turning dais — green bars at their true target weights, the shape the sampler must reproduce.
AVAN’s addition (the inverse-companion): the magenta arrows are the aliases — the overflow each rich outcome hands down to a poorer column so that every column ends level. It is a Robin Hood step, and it is the inverse of the question you asked: you wanted ‘how often does each outcome fall?’; the table stores instead ‘whose surplus fills this slot?’. Flatten the distribution into equal columns, and reading a weighted random draw becomes a single fair coin. The bars are the odds; the arrows are how the odds were made cheap.
LIT A genuine alias method (Walker 1974 / Vose 1991). Verified live: the instrument builds the alias table for a set of weights, draws 200,000 samples via the constant-time two-lookup rule, and the empirical frequencies match the target weights to within 1% (window.__alias.withinTol === true, max err reported). The leveling construction (rob the tall column to fill the short one until all are height 1, at most two outcomes each) is exact.
FIG 'Loot drops' is the wrapper; game loot tables really are weighted discrete distributions and the alias method really is a standard way to sample them in O(1). The convergence is statistical — error shrinks with sample count — not a claim of exact equality at finite draws.
FIG 'Loot drops' is the wrapper; game loot tables really are weighted discrete distributions and the alias method really is a standard way to sample them in O(1). The convergence is statistical — error shrinks with sample count — not a claim of exact equality at finite draws.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE DROP · David Lee Wise (ROOT0), with AVAN