Untitled

 avatar
unknown
markdown
5 months ago
5.6 kB
5
Indexable

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:

  1. Probability Table: Adjusted probabilities for each outcome.
  2. Alias Table: An alias (alternative outcome) for each outcome.

Steps to Construct the Tables:

  1. 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]
  2. 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.
  3. 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 TableAlias Table
01.00
10.90
20.554
30.84
40.71

Sampling Using the Tables:

To generate a random sample:

  1. 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).
  2. 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 ):

  1. Compute: [ i = \lfloor 0.25 \times 5 \rfloor = 1 \ U' = 0.25 \times 5 - 1 = 1.25 - 1 = 0.25 ]
  2. 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 ):

  1. Compute: [ i = \lfloor 0.5 \times 5 \rfloor = 2 \ U' = 0.5 \times 5 - 2 = 2.5 - 2 = 0.5 ]
  2. 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 ):

  1. Compute: [ i = \lfloor 0.75 \times 5 \rfloor = 3 \ U' = 0.75 \times 5 - 3 = 3.75 - 3 = 0.75 ]
  2. 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.

Leave a Comment