Untitled
Walker's Alias Method Simplified:
Walker's Alias Method is a clever technique to efficiently generate random samples from a discrete probability distribution in constant time. Here's a simple step-by-step explanation using the given probability distribution:
Given Probability Distribution:
We have 5 outcomes with probabilities:
- Outcome 0: 0.22
- Outcome 1: 0.24
- Outcome 2: 0.11
- Outcome 3: 0.16
- Outcome 4: 0.27
Goal:
We want to build two tables:
- Probability Table: Adjusted probabilities for each outcome.
- Alias Table: An alias (alternative outcome) for each outcome.
Steps to Construct the Tables:
-
Initialize:
- Number of outcomes, ( n = 5 ).
- Multiply each probability by ( n ) to get scaled probabilities: [ \text{Scaled Probabilities} = [1.1, 1.2, 0.55, 0.8, 1.35] ]
- Create two lists:
- Small: Indices where scaled probability < 1.
- Large: Indices where scaled probability ≥ 1.
- Initial lists:
- Small = [2, 3]
- Large = [0, 1, 4]
-
Process Small and Large Lists:
-
Iteration 1:
- Pop from Small: ( s = 3 )
- Pop from Large: ( l = 4 )
- Set: [ \text{Probability}[3] = 0.8 \ \text{Alias}[3] = 4 ]
- Adjust Scaled Probability of ( l ): [ \text{Scaled_Probabilities}[4] -= (1 - \text{Probability}[3]) \ \text{Scaled_Probabilities}[4] = 1.35 - 0.2 = 1.15 ]
- Since ( \text{Scaled_Probabilities}[4] ≥ 1 ), ( l = 4 ) remains in Large.
-
Iteration 2:
- Pop from Small: ( s = 2 )
- Pop from Large: ( l = 4 )
- Set: [ \text{Probability}[2] = 0.55 \ \text{Alias}[2] = 4 ]
- Adjust Scaled Probability of ( l ): [ \text{Scaled_Probabilities}[4] -= (1 - \text{Probability}[2]) \ \text{Scaled_Probabilities}[4] = 1.15 - 0.45 = 0.7 ]
- Since ( \text{Scaled_Probabilities}[4] < 1 ), add ( l = 4 ) to Small.
-
Iteration 3:
- Pop from Small: ( s = 4 )
- Pop from Large: ( l = 1 )
- Set: [ \text{Probability}[4] = 0.7 \ \text{Alias}[4] = 1 ]
- Adjust Scaled Probability of ( l ): [ \text{Scaled_Probabilities}[1] -= (1 - \text{Probability}[4]) \ \text{Scaled_Probabilities}[1] = 1.2 - 0.3 = 0.9 ]
- Since ( \text{Scaled_Probabilities}[1] < 1 ), add ( l = 1 ) to Small.
-
Iteration 4:
- Pop from Small: ( s = 1 )
- Pop from Large: ( l = 0 )
- Set: [ \text{Probability}[1] = 0.9 \ \text{Alias}[1] = 0 ]
- Adjust Scaled Probability of ( l ): [ \text{Scaled_Probabilities}[0] -= (1 - \text{Probability}[1]) \ \text{Scaled_Probabilities}[0] = 1.1 - 0.1 = 1.0 ]
- Since ( \text{Scaled_Probabilities}[0] = 1 ), no action needed.
-
-
Finalize Tables:
- For any remaining indices (here, index 0), set: [ \text{Probability}[0] = 1.0 \ \text{Alias}[0] = 0 ]
Final Probability and Alias Tables:
| Index (Outcome) | Probability Table | Alias Table |
|---|---|---|
| 0 | 1.0 | 0 |
| 1 | 0.9 | 0 |
| 2 | 0.55 | 4 |
| 3 | 0.8 | 4 |
| 4 | 0.7 | 1 |
Sampling Using the Tables:
To generate a random sample:
-
Generate a Uniform Random Number ( U ) in [0, 1):
- Compute ( i = \lfloor U \times n \rfloor ).
- Compute ( U' = U \times n - i ) (the fractional part).
-
Use the Tables:
- If ( U' < \text{Probability}[i] ), output outcome ( i ).
- Else, output outcome ( \text{Alias}[i] ).
Applying Inputs 0.25, 0.5, and 0.75:
Let's see what outcomes we get for each input.
Input ( U = 0.25 ):
- Compute: [ i = \lfloor 0.25 \times 5 \rfloor = 1 \ U' = 0.25 \times 5 - 1 = 1.25 - 1 = 0.25 ]
- Check: [ U' = 0.25 < \text{Probability}[1] = 0.9 \ \text{Since } 0.25 < 0.9, \text{ output outcome } 1. ]
Output: Outcome 1
Input ( U = 0.5 ):
- Compute: [ i = \lfloor 0.5 \times 5 \rfloor = 2 \ U' = 0.5 \times 5 - 2 = 2.5 - 2 = 0.5 ]
- Check: [ U' = 0.5 < \text{Probability}[2] = 0.55 \ \text{Since } 0.5 < 0.55, \text{ output outcome } 2. ]
Output: Outcome 2
Input ( U = 0.75 ):
- Compute: [ i = \lfloor 0.75 \times 5 \rfloor = 3 \ U' = 0.75 \times 5 - 3 = 3.75 - 3 = 0.75 ]
- Check: [ U' = 0.75 < \text{Probability}[3] = 0.8 \ \text{Since } 0.75 < 0.8, \text{ output outcome } 3. ]
Output: Outcome 3
Explanation:
- For each input ( U ), we determine which "slice" of the [0, 1) interval it falls into by computing ( i ).
- The fractional part ( U' ) tells us whether to accept the primary outcome (( i )) or switch to its alias (( \text{Alias}[i] )).
- The method ensures that over many samples, each outcome occurs with the correct probabilities specified in the original distribution.
Summary:
Walker's Alias Method efficiently samples from a discrete distribution by preprocessing it into probability and alias tables. Sampling then becomes a quick check using these tables, making it ideal for scenarios requiring numerous random draws from the same distribution.