How to Learn the Alias Method: Walker–Vose Tables, O(1) Discrete Sampling and Probability Buckets

Wait, What?

A weighted random choice can be reduced to one uniform bucket choice and one coin flip.

The alias method preprocesses a fixed discrete distribution so later samples can be generated in constant time. Its teaching value is larger than the trick itself: it shows how preprocessing can transform an expensive repeated query into a tiny runtime decision while preserving an exact probability distribution.

Quick Answer

Learn the alias method through normalise weights → scale probabilities by n → split entries into small and large groups → fill equal-probability buckets → store threshold and alias → sample a bucket uniformly → choose primary or alias by one random comparison.

1. Start With the Repeated-Sampling Problem

Suppose a fixed distribution must be sampled millions of times. A cumulative distribution plus binary search gives logarithmic lookup after preprocessing. The alias method spends more effort arranging the distribution into buckets so each later query uses constant work.

2. Scale the Probabilities

For n outcomes, multiply each normalised probability by n. Values below one are underfull buckets; values above one are overfull. The total scaled mass is exactly n, which means excess mass from large entries can fill deficits in small entries.

3. Pair Small and Large Entries

Take one underfull bucket and one overfull bucket. Store the underfull outcome as the bucket’s primary choice and fill the remaining bucket mass using the overfull outcome as its alias. Reduce the overfull entry by the amount transferred, then return it to the appropriate small or large group.

4. Understand the Sampling Step

Choose one bucket uniformly from n buckets. Then draw a uniform value inside that bucket. If it falls below the stored threshold, return the primary outcome; otherwise return the alias. The table construction guarantees that the total area assigned to each outcome equals its original probability mass.

5. Trace a Three-Outcome Distribution

Use a distribution such as 0.5, 0.3 and 0.2. Scale it to 1.5, 0.9 and 0.6. Build the buckets by hand and shade the primary and alias areas. This visual proof is the cleanest way to see why uniform bucket selection still produces non-uniform outcomes.

6. Separate Preprocessing Cost From Query Cost

The alias method is attractive when the distribution is reused. If weights change after every sample, rebuilding the table may dominate the workload. Learners should therefore state the update frequency before claiming constant-time sampling is a practical win.

7. Numerical and Randomness Details Matter

Real implementations must handle floating-point rounding, zero weights, normalisation and pseudorandom-number generation carefully. Vose’s construction is a well-known linear-time preprocessing approach, but correctness still depends on representing the intended distribution faithfully.

Common Failure States

• Forgetting to normalise input weights.
• Assuming every bucket contains one outcome only.
• Choosing buckets proportionally instead of uniformly after preprocessing.
• Rebuilding the table unnecessarily for a static distribution.
• Ignoring rounding drift when probabilities nearly sum to one.
• Claiming O(1) sampling while hiding expensive per-query updates to the weights.

Practice Ladder

• Normalise a four-weight distribution.
• Classify scaled entries as small or large.
• Build the alias table by hand.
• Calculate the final probability mass of each outcome from the bucket areas.
• Simulate many samples and compare empirical frequencies.
• Compare alias sampling with cumulative binary search for static and changing workloads.

Learning Hall Boundary

This article owns fast repeated sampling from a fixed discrete distribution. Reservoir sampling remains separate because it solves a streaming selection problem with unknown final input length rather than repeated draws from a known probability table.

Evidence Boundary

The mathematical method is exact under ideal probability arithmetic and suitable random draws. Practical systems should additionally verify numerical normalisation, generator quality, reproducibility requirements and whether the distribution changes frequently enough to make rebuilding expensive.

Professional rule: understand the alias method when you can reconstruct the bucket-filling argument, prove where each outcome’s probability mass lives and explain when preprocessing for O(1) sampling is actually worthwhile.