Alias Method Sampling

Alias Method Sampling

Mathematical Definition

For n nonnegative weights w_i with a positive total W, define p_i = w_i/W. The table stores a cutoff q_i ∈ [0, 1] and an alias a_i for each column. Draw J uniformly from the n columns and an independent U uniformly from [0, 1).

The first term counts the portion kept by column i. The sum counts portions redirected from all columns whose alias is i, including a self-alias if present. Equality at a cutoff takes the alias branch. For an ideal continuous uniform variable, equality has probability zero; its explicit treatment still matters for finite-precision code and boundary inputs.

Key Concepts

Building the table in linear time

1. Scale each probability to s_i = n p_i. The total scaled mass is n.
2. Put indices with s_i < 1 in a short list and the others in a long list.
3. Remove one short index l and one long index h. Set q_l = s_l and a_l = h.
4. Fill the missing mass 1 − s_l from h. Replace s_h by s_h + s_l − 1 and reclassify h.
5. Finish remaining unit-mass columns with cutoff 1 and a self-alias. Numerical roundoff may leave either list nonempty.

Each pairing finishes one column, so preprocessing takes O(n) time and O(n) memory. A single draw takes O(1) time under the usual constant-time arithmetic and random-number model. Updating weights requires rebuilding the table. Different pairing orders can produce different valid tables with exactly the same target distribution; this demonstration uses last-in-first-out lists.

An independently calculated example

Weights (1, 2, 3, 4) give probabilities (0.1, 0.2, 0.3, 0.4) and scaled masses (0.4, 0.8, 1.2, 1.6). Pair B with D, then A with D, then D with C. The cutoffs become (0.4, 0.8, 1, 0.8) and aliases (D, D, C, C). Each column has probability 1/4, so the reconstructed probabilities are:

In column A, coin 0.35 selects A, whereas coin 0.4 selects alias D. Notice that column D can redirect to C even though other columns redirect to D. A draw follows exactly one alias lookup; aliases are not followed recursively.

Boundaries and reproducibility

• Zero weights are valid. A zero-weight outcome has no area and cannot be drawn, even when its own column is selected.
• All-zero weights cannot be normalized. Negative, noninteger or empty weights are rejected by this demonstration, which limits each weight to integers from 0 to 20.
• Coin values must lie in [0, 1). Input 1 is invalid, not an extra endpoint of the uniform distribution.
• The batch uses mulberry32 with an explicit 32-bit seed and two consecutive uniform values per draw. Repeating a seed repeats the sample; changing the weights or batch settings clears the old sample.
• Observed frequencies fluctuate in a finite batch. Equal target and reconstructed probabilities establish the table algebra, while reproducible counts make implementation behavior inspectable.

Historical Context

Alastair J. Walker developed alias-based sampling methods in the 1970s. Michael D. Vose published a linear-time construction in 1991. The practical benefit comes from moving work into preprocessing when many draws share the same categorical distribution.

Real-world Applications

• Simulation: Repeatedly choose events or particle categories with fixed unequal probabilities.
• Machine learning: Sample items from a large fixed categorical proposal, such as a negative-sampling distribution.
• Games and procedural systems: Reuse weighted selections for loot, terrain or randomized content.

Related Concepts

• Probability Distributions: Defines the target probabilities that the alias representation preserves.
• Rejection Sampling: Accepts or rejects proposals; the alias method always returns a categorical outcome after a single column comparison.
• Monte Carlo Simulation: Uses repeated samples to estimate quantities; an alias table can provide its categorical draws.
• Law of Large Numbers: Explains convergence of empirical frequencies to target probabilities, rather than exact agreement in every finite batch.

References

• Walker (1977), An Efficient Method for Generating Discrete Random Variables with General Distributions.
• Vose (1991), A Linear Algorithm for Generating Random Numbers with a Given Distribution.
• Alias method: representation and construction.