Every other Probabilistic entry on this site spends randomness on a question about
one item at a time — has it been seen, how many times, is it similar to another. The
Alias Method answers a different kind of question entirely: given n outcomes with
arbitrary, fixed weights (a loaded die, a roulette wheel with unequal slices, a word list weighted
by frequency), draw repeatedly from that exact distribution, as fast as possible, forever.
The two obvious approaches both cost more per draw than they need to: build a running total (a
cumulative distribution) and scan it linearly until the target is passed —
O(n) per draw — or binary-search that same cumulative array the way Binary Search searches any sorted array —
O(log n) per draw, better, but still growing with n. The Alias Method,
introduced by Alistair Walker in 1974 and given an O(n)-time construction by Michael
Vose in 1991 (Walker's original needed a full sort, O(n log n)), reaches
true O(1) per draw, no matter how skewed the weights or how large
n is — genuinely optimal, since no algorithm can sample faster than constant
time or build a table without looking at every weight at least once.
The trick is a change of shape, not a clever search: instead of one array of cumulative
probabilities, build two flat arrays of length n —
prob[] and alias[]. A draw picks a uniformly random index
i in [0, n), flips one biased coin using prob[i], and
returns either i itself or the other outcome parked at alias[i]. Every
index is checked exactly once, every draw does exactly one random index pick and one coin flip —
the weight skew that would slow down a scan or a binary search is entirely absorbed into the
construction step, once, and never touched again.
A fixed 5-outcome distribution — apple, banana, cherry, date, elderberry, weighted 1, 2, 3, 4,
10 (total 20) — walked through Vose's construction one pairing at a time. Each outcome's weight is
first rescaled to n·weight/total so the five values average exactly 1: apple 0.25,
banana 0.5, cherry 0.75 start in the "small" pile (below 1), date 1.0 and elderberry 2.5 start in
"large" (1 or above). Click Next to watch each step pop one from each pile,
lock in that small index's row, and hand its leftover probability mass to the large index, which
then goes back into whichever pile its new value belongs to.
| item | weight | scaled share | prob[i] | alias[i] |
|---|
Once the table above is complete, it's a working alias table for these five weights. The demo below draws from it directly — one random index, one coin flip, repeated as many times as you like — and tracks the running frequency against the true weighted proportions.
| item | expected | observed | draws |
|---|
weight / total),
then multiply every one by n. The five values now average exactly 1 by construction —
some fall below 1 ("small"), some at or above 1 ("large") — and that shared average of 1 is the
whole reason the algorithm terminates cleanly: every unit of probability mass "borrowed" from a
large item to top off a small one is accounted for exactly once.s is now fully resolved: prob[s] is its own scaled
share, alias[s] points at the large index l that's covering the rest of
its column. Subtract what was just borrowed (1 - scaled[s]) from
scaled[l], and push l back into whichever pile its new value now
belongs to — it may still have enough left to cover another small item, or it may itself have
dropped below 1.prob[i] = 1 directly and no alias at all:
picking that index is already picking that outcome, a coin flip would just add noise. Every index
is popped and resolved exactly once, so construction is n pairing/leftover steps
total for n outcomes — linear time, no sorting anywhere, which is exactly Vose's
improvement over Walker's original O(n log n) construction.class AliasMethod {
constructor(weights) {
const n = weights.length;
const total = weights.reduce((a, b) => a + b, 0);
const scaled = weights.map(w => (w / total) * n);
this.prob = new Array(n).fill(1); // leftovers default to 1, no alias needed
this.alias = new Array(n).fill(-1);
const small = [], large = [];
scaled.forEach((p, i) => (p < 1 ? small : large).push(i));
while (small.length && large.length) {
const s = small.pop();
const l = large.pop();
this.prob[s] = scaled[s];
this.alias[s] = l;
scaled[l] -= (1 - scaled[s]);
(scaled[l] < 1 ? small : large).push(l);
}
}
sample() {
const i = Math.floor(Math.random() * this.prob.length);
return Math.random() < this.prob[i] ? i : this.alias[i];
}
}Verified three ways in Node before any page prose was written. (1) Constructing this exact
class on the demo's own weights [1, 2, 3, 4, 10] reproduces the shown table exactly:
prob = [0.25, 0.5, 0.75, 1, 1], alias = [4, 4, 4, -1, -1]. (2) 300,000
calls to sample() on that table land at 5.01% / 9.92% / 14.95% / 20.11% / 50.01%,
against true weighted proportions of 5% / 10% / 15% / 20% / 50%. (3) A separate step-generator
that produces the same table one pairing at a time (driving the Try it demo
above) was checked to reach the identical final prob[]/alias[] as this
class, not just a plausible-looking one — the two are independent implementations of the same
algorithm, and disagreeing would have meant one of them was wrong. See
/tmp/alias/*.js, scratch, not committed.
Forgetting to multiply by n silently collapses every draw to uniform —
no error, no crash, just the wrong distribution. The scaling step exists specifically so
the piles' shared average lands at exactly 1; skip the * n and use raw probabilities
(which sum to 1, not to n) instead, and every value except a single outcome holding
essentially all the weight ends up under 1 — the "large" pile starts empty, the construction's
while loop never runs at all, and every index falls straight through to the
"leftover" branch, which sets prob[i] = 1 for all of them. The resulting table has no
aliases at all and prob[i] = 1 everywhere, which means the coin flip always returns
i itself — sampling degrades into nothing but the uniform random index pick, with the
real weights thrown away entirely. Measured directly on the same five weights: a correctly-scaled
table's 300,000 draws land at 5.0% / 9.9% / 15.0% / 20.0% / 50.1% as expected; the unscaled table's
300,000 draws land at 20.1% / 20.0% / 20.0% / 20.0% / 20.0% — dead even, exactly what discarding
the weights and picking a uniform index would produce. Nothing about the unscaled build throws or
looks obviously broken; only a frequency check across many draws exposes it.
| item | expected | correct (measured) | no-scale bug (measured) |
|---|---|---|---|
| Not run yet — click above. | |||
An alias table doesn't support changing one weight in place — it needs a full rebuild,
because every column is coupled to whichever other column it borrowed from. It's tempting
to treat a weight update the way a plain cumulative-probability array might: find the one changed
outcome and patch just its own entry. But prob[] and alias[] encode the
whole distribution jointly — an outcome's column can hold another outcome's leftover mass, and
that other outcome's own column has no idea its partner's weight just changed. Patched in place,
only the one touched cell changes; every other cell, including any column that happens to alias
into the changed index, keeps routing draws exactly as it did under the old weights. Measured:
starting from the same [1, 2, 3, 4, 10] table above, then raising elderberry's weight
from 10 to 40 (new true proportions 2% / 4% / 6% / 8% / 80%) — a freshly rebuilt table's 300,000
draws land at 2.0% / 4.1% / 6.0% / 8.1% / 79.9%, correctly tracking the new weights, while a table
with only prob[4] patched to reflect elderberry's new share still draws 5.1% / 10.0% /
15.0% / 20.1% / 49.9% — indistinguishable from the old distribution, because apple's,
banana's, and cherry's own columns still each alias into elderberry using the old, un-rebuilt
split. Any update to the underlying weights needs a full O(n) reconstruction, the
same cost as building the table the first time — there's no cheaper incremental path.
| item | expected (new weights) | rebuilt (measured) | naive patch (measured) |
|---|---|---|---|
| Not run yet — click above. | |||
A quieter, honest footnote on the leftover step: the "leftovers land within
floating-point error of exactly 1" claim above was checked, not assumed — a sweep from
n = 10 up to n = 1,000,000 on random weights found the drift on a
leftover index growing with n but staying minuscule throughout (about
4×10-16 at n = 10, about 2.6×10-8 at n = 1,000,000)
— never enough to flip which pile an index would belong to, or to leave both piles non-empty at
once. That's exactly why the reference implementation above assigns leftovers
prob[i] = 1 directly instead of checking scaled[i] === 1 or trusting the
arithmetic to land there exactly: the drift is real and measured, just never large enough at any
practical n to matter on its own — the robustness comes from not depending on exact
equality in the first place, not from the drift happening to stay small.
O(1) regardless of vocabulary size or how skewed word frequencies are (and natural
language word frequencies are famously skewed).O(1) per draw instead of O(n).n things, weighted,
over and over, from weights that don't change between picks" — precisely the shape this structure
is built for.Construction: O(n) time and space — each of the n
outcomes is pushed onto exactly one pile once and popped exactly once, with O(1) work
per pop (Vose's refinement over Walker's original method, which needed a full
O(n log n) sort of the probabilities first). Sampling:
O(1) time per draw, always — one uniform integer in [0, n), one coin
flip, one conditional branch, regardless of n or how skewed the weights are. That's
strictly better than a cumulative-sum array's O(log n) binary-search-per-draw, and
the two share the same O(n) space cost, so there's no space trade being made to get
there. The one real limitation is exactly the second Pitfall
above: no incremental update. Changing any single weight requires rebuilding the whole table from
scratch, O(n) again — the Alias Method is the right structure when the distribution
is fixed for a long run of draws, and the wrong one when weights change every few samples.
This site's guide, Choosing a Probabilistic Structure, calls this entry out as a standalone fourth question rather than a competitor to the stream-summarization family above — every other entry in the guide builds up state from a stream one item at a time, while this one takes a whole, already-known distribution up front and answers "draw from this, repeatedly, in O(1)."