Overview
The Alias Method builds probability and alias tables so each draw chooses one column and then one of two outcomes.
CoreSource checked
Alias Method
Samples from a discrete weighted distribution in constant time after preprocessing.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Randomness & Sampling
- Difficulty
- Intermediate
- Family
- Discrete Sampling
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 1
- Relationships
- 4
- Code example
- Ready
- Visualization
- Ready
- Aliases
- Walker's Alias Method
Core Concepts
weighted distributionalias tablepreprocessingconstant-time draw
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(1) per sample after preprocessing
Worst
O(n)
Space
O(n)
When to Use
- Use when many samples are drawn from the same discrete weighted distribution.
- Use when weighted random selection is a central requirement.
When Not to Use
- Avoid when weights change after nearly every draw.
- Avoid when the output distribution is not the one the downstream task actually needs.
What It Does
- Normalizes weights
- Builds probability and alias tables
- Draws weighted outcomes in O(1) time
Use Cases
- Weighted random selection
- Game loot tables
- Fast categorical sampling
Inputs
- Discrete outcomes
- Nonnegative weights
Outputs
- Randomly selected outcome
Key Formulas (1)
Scaled weight
scaledweight i = weighti · n / ∑(weights)
scaled_weight_i = weight_i * n / sum(weights)Converts weights into table-column probabilities.
Pseudocode
- 1.Scale weights by the number of outcomes
- 2.Split outcomes into small and large worklists
- 3.Fill alias table columns by pairing small and large weights
- 4.For each sample, choose a random column and a random threshold
- 5.Return either the column outcome or its alias
Canonical Example
- Input
- weights = A:0.75, B:0.25
- Output
- sample uses one table column and threshold
- Explanation
- The preprocessed table returns A more often while each draw stays constant time.
Implementation Notes
- Normalize carefully enough that small floating-point leftovers do not break table construction.
- Use repeatable seeds for tests and check distribution summaries.
- Keep a tiny example with expected output beside the implementation.
Common Pitfalls
- Negative weights or all-zero weights need explicit rejection before preprocessing.
- Biased random choices can look plausible while producing wrong statistics.
- Not defining boundary, empty, or degenerate inputs before implementation.
Interactive Mechanism Walkthrough
Sequence Window & Automaton AlignmentShow each table column split between a primary outcome and an alias outcome.
Input:ABABABCABAB
Window:ABAB
Step 1 of 5: Scale weights by the number of outcomes
sampling-patternNotes
Weight changes require rebuilding or updating the tables.
Sources (2)
What each reference supports for this entry.
Vose Alias Method
PaperReference for constructing alias tables for constant-time discrete sampling.
Open sourceNon-Uniform Random Variate Generation
BookRandom variate generation reference for Alias Method's distribution-sampling mechanism and acceptance or transform rules.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageAlternative toInverse Transform Sampling
Alias tables avoid a cumulative search for each discrete draw.
SpecializesMultinomial Sampling
The alias method accelerates repeated draws from a discrete weighted distribution.
Related Algorithms
Tags
RandomnessSamplingWeighted Sampling