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!
๐ 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
โก 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.