Simulating Discrete Random Variables

Alias Method and Generating Random Vectors

Sravan Danda

CS&IS and APPCAIR, BITS-Pilani, Goa, India

October 10, 2022

Simulating Discrete Random Variables

Outline

1 Recap

2 The Alias Method for Generating Discrete Random Variables

3 Generating Random Vectors

4 Summary and What Next?

Simulating Discrete Random Variables
Recap

Recap · · ·

1 Simulating Discrete Random Variables

1 Inverse Transform Method
1 Poisson Random Variable
2 Binomial Random Variable
2 The Acceptance-Rejection Technique
3 The Composition Approach
Simulating Discrete Random Variables
The Alias Method for Generating Discrete Random Variables

The Alias Method

The set-up
1 Suppose P, P(k) , Q(k) , k ≤ n − 1 represent [Link] on the
integers {1, 2, · · · , n}
2 The vector P(k) has at most k non-zero components
3 The vector Q(k) has at most 2 non-zero components
Alias-Method: Any probability mass function P can be
represented as an equally weighted mixture of n − 1 probability
mass functions Q i.e. P can be expressed as:

1 n−1
X
P= Q(k) (1)
n − 1 k=1
Simulating Discrete Random Variables
The Alias Method for Generating Discrete Random Variables

The Alias Method: Visualization

Screenshot Source 1

1
[Link]
discrete-random-variables
Simulating Discrete Random Variables
The Alias Method for Generating Discrete Random Variables

The Alias Method: Visualization

Screenshot Source 2

2
[Link]
discrete-random-variables
Simulating Discrete Random Variables
The Alias Method for Generating Discrete Random Variables

The Alias Method: Visualization

Screenshot Source 3

3
[Link]
discrete-random-variables
Simulating Discrete Random Variables
The Alias Method for Generating Discrete Random Variables

The Alias Method: Practical Implications of the

Decomposition

Constructing the table: O(n) and simulation4 O(1)

1 Generate U1 and set N = 1 + b(n − 1)U1 c
2 Generate U2 and set

(N)
 iN if U2 < QiN
X= (2)
 jN otherwise

Here the values iN and jN correspond to the points in the support

of Q (N)

4
inverse transform method requires O(n) for both construction and simulating a new data point
Simulating Discrete Random Variables
The Alias Method for Generating Discrete Random Variables

The Alias Method: Main Result

Lemma
Let P = {Pi , i = 1, 2, · · · , n} denote a p.m.f. Then
1 there exists an i, 1 ≤ i ≤ n such that Pi < 1/(n − 1)
2 For this i, there exists j with j 6= i such that
Pi + Pj ≥ 1/(n − 1)

Proof.

1 If all probabilities are at least as large as 1/(n − 1) their sum

would exceed 1 which is a contradiction
2 If for all j 6= i, the sum Pi + Pj < 1/(n − 1),
P n−1
j6=i (Pi + Pj ) < n−1 which is a contradiction as the LHS is
(n − 2)Pi + 1 > 1
Simulating Discrete Random Variables
The Alias Method for Generating Discrete Random Variables

The Alias Method: Construction

Choose i and j satisfying the conditions of Lemma. Set5

(1)
Qi = (n − 1)Pi (3)

(1)
Qj = 1 − (n − 1)Pi (4)

Decomposition at step 1
1 n − 2 (n−1)
P= Q(1) + P (5)
n−1 n−1

where P(n−1) denotes the remaining mass

5
all mass of i is associated to the first of Qs. The conditions on i and j ensure that these values lie between 0
and 1
Simulating Discrete Random Variables
The Alias Method for Generating Discrete Random Variables

The Alias Method: Construction Continued · · ·

Next
(n−1)
Pi =0 (6)

n−1 1 n−1 1
   
(n−1) (1)
Pj = Pj − Qj = Pi + Pj −
n−2 n−1 n−2 n−1
(7)
This is non-negative from the Lemma

(n−1) n−1
Pk = Pk , k ∈
/ {i, j} (8)
n−2
Simulating Discrete Random Variables
The Alias Method for Generating Discrete Random Variables

The Alias Method: Construction Continued · · ·

Repeating the procedure

1 n − 3 (n−2)
P(n−1) = Q(2) + P (9)
n−2 n−2
So
1 1 n − 3 (n−2)
P= Q(1) + Q(2) + P (10)
n−1 n−1 n−1
Hence
1  (1) 
P= Q + Q(2) + · · · + Q(n−1) (11)
n−1
Simulating Discrete Random Variables
The Alias Method for Generating Discrete Random Variables

The Alias Method: Some Remarks

1 The {Q (k) } can be reordered such that Q (k) assigns positive

weight to k. Hence the name alias.
2 It is not necessary to generate a second random number as
N − 1 is the integer part of (n − 1)U1 and (n − 1)U1 − (N − 1)
is independent of U1 . This can be used in the second step.
Simulating Discrete Random Variables
Generating Random Vectors

Generating Random Vectors

Idea: Generate random variables by sequential conditioning: X1

followed by X2 |X1 followed by X3 |X1 , X2 and so on · · ·
Example: Consider n independent trials T1 , · · · , Tn each of which
results in one of the outcomes 1, 2, · · · , r with respective
probabilities p1 , p2 · · · , pr . Define

Xi = |{Tt : Tt = i, 1 ≤ t ≤ n}| (12)

Interested in generating (X1 , X2 , · · · , Xr ). Clearly, the random
variables are dependent.
Simulating Discrete Random Variables
Generating Random Vectors

Generating Random Vectors: Example Continued · · ·

r
n! x1 xr
X
P{X1 = x1 , · · · , Xr = xr } = p · · · pr , xi = n (13)
x1 ! · · · xr ! 1 i=1

Best way to simulate depends on relative sizes of r and n

1 r is large relative to n
2 n is large relative to r
Simulating Discrete Random Variables
Generating Random Vectors

Generating Random Vectors: Example Continued · · ·

r is large relative6 to n

1 Generate independent random variables Y1 , · · · , Yn such that

P{Yj = i} = pi , i = 1, · · · , r , j = 1, · · · , n (14)

2 Count the number of Y s that take the value i

Xi = |{Yj : Yj = i, j = 1, · · · , n}| (15)

6
many of the outcomes are zeros
Simulating Discrete Random Variables
Generating Random Vectors

Generating Random Vectors: Example Continued · · ·

n is large relative to r

X1 ∼ Binomial(n, p1 ) (16)

p2
X2 |X1 = x1 ∼ Binomial(n − x1 , ) (17)
1 − p1

p2
X3 |X1 = x1 , X2 = x2 ∼ Binomial(n − x1 − x2 , ) (18)
1 − p1 − p2
Question: Can you find the breaking point on the relative sizes of
r to n at which one of these two methods outperforms the other?
Simulating Discrete Random Variables
Summary and What Next?

Summary

1 Simulating Discrete Random Variables

1 The Alias Method for Generating Discrete Random Variables
2 Generating Random Vectors
Simulating Discrete Random Variables
Summary and What Next?

What Next?

Simulating Continuous Probability Distributions

1 Inverse transform algorithm
2 Rejection method
3 Normal random variable simulation