๐ The Alias Method
O(1) sampling after O(K) setup โ restructuring probability into equal-height cups
โ๏ธ Controls
Classic textbook example showing varied probabilities. Watch how underfilled cups get topped up by overfilled ones.
๐ฅ Small Queue (underfilled: q < 1)
๐ค Large Queue (overfilled: q โฅ 1)
๐ก Current Step
Click "Reset" to initialize, then "Step" to walk through the setup algorithm, or "Auto Play" to watch it unfold.
๐ฅค Probability Cups
Original Probabilities (scaled by K=8)
๐ฏ The Core Insight
After scaling by K, we restructure into K cups of height 1. Each cup holds probability from at most two original outcomes, enabling constant-time sampling.
๐ The Invariant
Let q[i] = Kยทp[i]. Each step transfers exactly (1 โ q[j]) from a large cup โ to fill a small cup j, preserving ฮฃq[i] = K and ensuring each cup ends at height 1 with at most two labels.
๐ Alias Table
| Cup i | prob[i] | alias[i] |
|---|
0
Pairings
-
Small Left
-
Large Left
0%
Progress
๐ฏ Alias Method Complexity
Setup:
O(K)
Per sample:
O(1)
Space:
O(K)
๐ฅค Sampling from Balanced Cups
Sampled Outcome
โ
Original Distribution (target)
What we want to sample
Restructured Cups (each has total height = 1)
Sampled Distribution (n = 0)
Bars: observed | Gold lines: true P
๐ Compare the Three Views
Top: Original PMF โ the distribution we want.
Middle: Restructured cups โ all height 1, but same colors show where probability came from.
Bottom: Sample histogram โ should converge to the original PMF!
Middle: Restructured cups โ all height 1, but same colors show where probability came from.
Bottom: Sample histogram โ should converge to the original PMF!
๐ O(1) Sampling Process
Step 1: Generate U ~ Uniform(0, K)
One random number gives us everything
U = ?
Step 2: Select Cup
Index i = โUโ โ {0,1,...,Kโ1} โ Cup (i+1)
i = ?
Step 3: Position in Cup (V = U โ i)
Fractional part V โ [0,1) is our "coin flip"
V = ?
Step 4: Compare V with prob[i]
V < prob[i] โ native, else โ alias
V ? prob[i]
Step 5: Return Result
Output k โ {1,...,K} in constant time!
Result = ?
0
Total Samples
0
Native Hits
0
Alias Hits
โ๏ธ Comparison: Steps per Sample
Alias Method:
1 lookup + 1 compare
Binary Search:
โlogโ 8โ = 3 comparisons
Linear Search:
1โ8 comparisons
For K=8, methods are similar. Alias shines when K is large!
๐ Index vs Cup Number
Arrays use 0-based index: i โ {0, 1, ..., 7}
Cups use 1-based labels: Cup k โ {1, 2, ..., 8}
Conversion: Cup k = i + 1
Cups use 1-based labels: Cup k โ {1, 2, ..., 8}
Conversion: Cup k = i + 1
โก Performance Benchmark: Alias vs Binary vs Linear
Compare setup cost (one-time) vs sampling cost (per sample). The alias method has O(K) setup but O(1) sampling โ watch it win as sample count grows!
Distribution Preview (first 50 of K)
PMF (top) / CDF (bottom)
โ
โ ๏ธ Browser Note
JavaScript has overhead. Real compiled code shows even larger alias method wins.
๐ง Setup vs Sampling Breakdown
Method
Setup
Sampling
Total
Click "Run Benchmark" to see timing breakdown
Theoretical Complexity: Comparisons per Sample
Amortized Cost: Setup + Sampling over N samples