END322E System Simulation
Class 9: Random Variate Generation
Housekeeping
• Reading assignment: Chapter 8 (BCNN)
END322E System Simulation 2
Random Variate Generation
• Goal: Use U(0,1) numbers to generate observations (variates) from
other distributions, and even stochastic processes.
• Discrete distributions, like Bernoulli, Binomial, Poisson, and empirical
• Continuous distributions like exponential, normal (many ways), and empirical
• Some widely-used techniques for generating random variates:
• Inverse-transform technique
• Acceptance-rejection technique
• Other Special techniques
• Direct Transformation, Convolution
END322E System Simulation 3
Inverse-transform Technique
• The concept:
r = F(x)
• For cdf function: r = F(x)
• Generate r from uniform (0,1) r1
• Find x:
x1
END322E System
4 Simulation
Inverse-transform Technique
• F(X) may not be 1-on-1 or strictly increasing.
• So,
• This representation can be applied to continuous or discrete or mixed
distributions.
• Inverse Transformation:
• Step 1: Sample U from U(0,1)
• Step 2: Return 𝑋 = 𝐹 −1 (𝑈)
END322E System Simulation 5
Continuous Uniform Distribution
• U(a,b)
END322E System Simulation 6
Exponential Distribution
• Exponential Distribution:
• Exponential cdf:
• To generate X1, X2, X3 …
END322E System Simulation 7
Exponential Distribution
• Example: Generate 200 variates Xi with distribution exp(l= 1)
• Generate 200 Rs with U(0,1) and utilize equation, the histogram of Xs become:
END322E System Simulation 8
Triangular distribution
END322E System Simulation 9
Try – Weibull Distribution
END322E System Simulation 10
Normal Distribution
• Unfortunately, the inverse c.d.f. of standard normal distribution does
not have an analytical form. This is often a problem with the inverse
transform method.
• Easy solution: Do a table lookup. E.g., If U= 0.975, then Z=1.96.
• A simple approximation:
• The following approximation gives at least one decimal place of
accuracy for 0.00134≤U≤0.98865
END322E System Simulation 11
Discrete Distributions
• It’s often best to construct a table.
• Example: Bernoulli distribution (p)
END322E System Simulation 12
Empirical Discrete Distribution
• The probability mass function (pmf) p(x):
p(-1)=0.6, p(2.5)=0.3, p(4)=0.1
END322E System Simulation 13
Discrete Uniform Distribution
• The discrete uniform distribution on {1,2,…,k} with pmf
1
𝑝 𝑥 = , 𝑥 = 1,2, … , 𝑘
𝑘
END322E System Simulation 14
Geometric Distribution
• The geometric distribution with a pmf
𝑝 𝑥 = 𝑝(1 − 𝑝)𝑥 , 𝑥 = 0,1,2, …
END322E System Simulation 15
Convolution Method
• Convolution means adding things up!
• For probability distributions of sum of independent RVs
• Example: Binomial from Bernoulli.
• Use inverse transformation to get Bernoulli Xi’s
• Add them to create Binomial
• Example: Erlang(λ)
END322E System Simulation 16
Acceptance-Rejection technique
• Useful particularly when inverse cdf does not exist in closed form, a.k.a. thinning
• Example: To generate random variates, X ~ U(1/4, 1)
Generate R
no
Condition
yes
Output R’
• R does not have the desired distribution, but R conditioned (R’) on the event {R ¼} does.
• Efficiency: Depends heavily on the ability to minimize the number of rejections.
END322E System
17 Simulation
Poisson Distribution (A-R Method)
• The Poisson distribution with pmf
END322E System Simulation 18
Poisson Distribution (A-R Method)
END322E System Simulation 19
Poisson Distribution (A-R Method)
• A-R algorithm:
END322E System Simulation 20
Non-stationary Poisson Process (NSPP)
• Non-stationary Poisson Process (NSPP): a Poisson arrival process with an arrival rate that
varies with time
• Example: Restaurants during lunch and dinner hours
• Idea behind thinning:
• Generate a stationary Poisson arrival process at the fastest rate, l* = max l(t)
• But “accept” only a portion of arrivals, thinning out just enough to get the desired time-varying
rate
Generate E ~ Exp(l*)
t=t+E
no
Condition
R <= l(t)
yes
Output E ’~ t
END322E System
21 Simulation
NSPP Thinning Algorithm
END322E System Simulation 22
Special Properties
• Based on features of particular family of probability distributions
• For example:
• Direct Transformation for normal and lognormal distributions
• Beta distribution (from gamma distribution)
END322E System
23 Simulation
Direct Transformation
• Approach for normal(0,1) – Box-Muller Method
• Consider two standard normal random variables, Z1 and Z2, plotted as a point in the
plane:
In polar coordinates:
Z1 = B cos f
Z2 = B sin f
• B2 = Z21 + Z22 ~ chi-square distribution with 2 degrees of freedom = Exp(l = 2). Hence,
• The radius B and angle f are mutually independent.
Z1 = (−2 ln R)1/ 2 cos(2R2 )
B = (−2 ln R )1/ 2
Z 2 = (−2 ln R)1/ 2 sin(2R2 )
END322E System Simulation 24
Direct Transformation
• Approach for normal(m,s2):
• Generate Zi ~ N(0,1)
• Approach for lognormal(m,s2):
• Generate X ~ N((m,s2)
END322E System
25 Simulation