Overview
Alias table construction splits probabilities into small and large buckets and fills table columns with a primary outcome plus an alias. Sampling then needs one random column and one biased coin flip.
CoreSource checked
Alias Table Construction
Preprocesses a discrete distribution so weighted samples can be drawn in constant time.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Randomness & Sampling
- Difficulty
- Intermediate
- Family
- Discrete Sampling
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 2
- Code example
- Ready
- Visualization
- Ready
Core Concepts
weighted random samplingdiscrete samplingdynamic programmingrandom samplingrandomness sampling
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(n log n)
Worst
O(n^2)
Space
O(n)
When to Use
- Use when the distribution is reused for many samples.
- Use when O(n) preprocessing is acceptable to get O(1) draws.
When Not to Use
- Avoid when weights change after nearly every sample.
- Avoid when a prefix-sum sampler is simpler and fast enough.
What It Does
- Normalizes weights into table-sized probabilities
- Pairs underfull and overfull buckets
- Builds probability and alias arrays for O(1) sampling
Use Cases
- Repeated weighted random selection
- Game loot tables and simulation events
- Discrete distributions sampled many times after preprocessing
Inputs
- Discrete probability or weight array w[0..n-1]
- Uniform random number generator
Outputs
- Precomputed probability and alias lookup tables (prob[], alias[])
- O(1) sampled category indices
Key Formulas (1)
Alias sampling decision
return column if u < probability[column] else alias[column]
return column if u < probability[column] else alias[column]Uses one random column and one threshold comparison per draw.
Pseudocode
- 1.Normalize weights so their average scaled probability is 1
- 2.Put underfull columns in a small stack and overfull columns in a large stack
- 3.Pair one small column with one large column
- 4.Store the small probability and large column as its alias
- 5.Adjust the large column and repeat until stacks are empty
Canonical Example
- Input
- weights A=1, B=3
- Output
- a two-column alias table that samples B about 75% of the time
- Explanation
- The table packs the unequal probabilities into fixed-size columns for constant-time draws.
Implementation Notes
- Validate nonnegative weights and positive total weight.
- Store probability and alias arrays separately.
- Test empirical frequencies against a tiny known distribution.
Common Pitfalls
- Forgetting to normalize weights causes biased tables.
- Floating-point rounding can leave small or large stacks slightly inconsistent.
- Negative or all-zero weights must be rejected before construction.
Interactive Mechanism Walkthrough
Iterative Convergence & State TrajectoryShow precomputing probability and alias columns for constant-time sampling on a small weighted random sampling example.
Step 1 of 5: Normalize weights so their average scaled probability is 1
randomness-sampling-mechanismNotes
Alias tables are a preprocessing tradeoff: fast draws for distributions that stay fixed.
Sources (1)
What each reference supports for this entry.
Non-Uniform Random Variate Generation
BookRandom variate generation reference for Alias Table Construction alias tables for constant-time discrete distribution sampling.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageVariant ofMultinomial Sampling
Alias tables are a fast method for repeated categorical or multinomial draws.
Alternative toInverse Transform Sampling
Inverse transform can sample from cumulative weights, while alias tables preprocess for constant-time draws.
Related Algorithms
Tags
Randomness & SamplingRandomness