Chapter 8
Random-Variate Generation
Banks, Carson, Nelson & Nicol
Discrete-Event System Simulation
Purpose & Overview
Develop understanding of generating samples
from a specified distribution as input to a
simulation model.
Illustrate some widely-used techniques for
generating random variates.
Inverse-transform
technique
Acceptance-rejection technique
Special properties
Inverse-transform Technique
The concept:
For
cdf function: r = F(x)
Generate r from uniform (0,1)
Find x:
x=
F-1(r)
r = F(x)
r1
x1
Exponential Distribution
[Inverse-transform]
Exponential Distribution:
Exponential cdf:
r=
=
F(x)
1 e-x
for x 0
To generate X1, X2, X3
Xi =
=
F-1(Ri)
-(1/) ln(1-Ri)
[Eqn 8.3]
Figure: Inverse-transform
technique for exp( = 1)
Exponential Distribution
[Inverse-transform]
Example: Generate 200 variates Xi with distribution
exp(= 1)
Generate 200 Rs with U(0,1) and utilize eqn 8.3, the histogram of
Xs become:
Check: Does the random variable X1 have the desired
distribution?
P( X 1 x0 ) = P( R1 F ( x0 )) = F ( x 0 )
5
Other Distributions
[Inverse-transform]
Examples of other distributions for which inverse
cdf works are:
Uniform
distribution
Weibull distribution
Triangular distribution
Empirical Continuous Distn
When theoretical distribution is not applicable
To collect empirical data:
[Inverse-transform]
Resample the observed data
Interpolate between observed data points to fill in the gaps
For a small sample set (size n):
Arrange the data from smallest to largest
x (1) x (2) x (n)
Assign the probability 1/n to each interval
x (i-1) x x (i)
(i 1)
X = F 1 ( R) = x(i 1) + ai R
where
ai =
x( i ) x( i 1)
1 / n (i 1) / n
x( i ) x( i 1)
1/ n
7
Empirical Continuous Distn
[Inverse-transform]
Example: Suppose the data collected for100 brokenwidget repair times are:
Cumulative Slope,
ai
Frequency, c i
Interval
(Hours)
Frequency
Relative
Frequency
0.25 x 0.5
31
0.31
0.31
0.81
0.5 x 1.0
10
0.10
0.41
5.0
1.0 x 1.5
25
0.25
0.66
2.0
1.5 x 2.0
34
0.34
1.00
1.47
Consider R1 = 0.83:
c3 = 0.66 < R1 < c4 = 1.00
X1 = x(4-1) + a4(R1 c(4-1))
= 1.5 + 1.47(0.83-0.66)
= 1.75
Discrete Distribution
[Inverse-transform]
All discrete distributions can be generated via
inverse-transform technique
Method: numerically, table-lookup procedure,
algebraically, or a formula
Examples of application:
Empirical
Discrete
uniform
Gamma
Discrete Distribution
[Inverse-transform]
Example: Suppose the number of shipments, x, on the
loading dock of IHW company is either 0, 1, or 2
Data - Probability distribution:
x
p(x)
F(x)
0
1
2
0.50
0.30
0.20
0.50
0.80
1.00
Method - Given R, the generation
scheme becomes:
R 0.5
0,
x = 1, 0.5 p R 0.8
2, 0.8 p R 1.0
Consider R1 = 0.73:
F(xi-1) < R <= F(xi)
F(x0) < 0.73 <= F(x1)
Hence, x1 = 1
10
Acceptance-Rejection technique
Useful particularly when inverse cdf does not exist in closed
form, a.k.a. thinning
Illustration: To generate random variates, X ~ U(1/4, 1)
Generate R
Procedures:
no
Step 1. Generate R ~ U[0,1]
Condition
Step 2a. If R >= , accept X=R.
yes
Step 2b. If R < , reject R, return
to Step 1
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.
NSPP
Output R
11
[Acceptance-Rejection]
Non-stationary Poisson Process (NSPP): a Possion arrival
process with an arrival rate that varies with time
Idea behind thinning:
Generate a stationary Poisson arrival process at the fastest rate,
* = max (t)
But accept only a portion of arrivals, thinning out just enough to
get the desired time-varying rate
Generate E ~ Exp(*)
t=t+E
no
Condition
R <= (t)
yes
Output E ~ t
12
NSPP
[Acceptance-Rejection]
Example: Generate a random variate for a NSPP
Data: Arrival Rates
t
(min)
Mean Time
Between
Arrivals
(min)
15
1/15
Arrival
Rate (t)
(#/min)
60
12
1/12
120
1/7
180
1/5
240
1/8
300
10
1/10
360
15
1/15
420
20
1/20
480
20
1/20
Procedures:
Step 1. * = max (t) = 1/5, t = 0 and i = 1.
Step 2. For random number R = 0.2130,
E = -5ln(0.213) = 13.13
t = 13.13
Step 3. Generate R = 0.8830
(13.13)/*=(1/15)/(1/5)=1/3
Since R>1/3, do not generate the arrival
Step 2. For random number R = 0.5530,
E = -5ln(0.553) = 2.96
t = 13.13 + 2.96 = 16.09
Step 3. Generate R = 0.0240
(16.09)/*=(1/15)/(1/5)=1/3
Since R<1/3, T1 = t = 16.09,
and i = i + 1 = 2
13
Special Properties
Based on features of particular family of
probability distributions
For example:
Direct
Transformation for normal and lognormal
distributions
Convolution
Beta distribution (from gamma distribution)
14
Direct Transformation
[Special Properties]
Approach for normal(0,1):
Consider two standard normal random variables, Z1 and Z2,
plotted as a point in the plane:
In polar coordinates:
Z1 = B cos
Z2 = B sin
B2 = Z21 + Z22 ~ chi-square distribution with 2 degrees of freedom
= Exp( = 2). Hence, B = (2 ln R )1/ 2
The radius B and angle are mutually independent.
Z1 = (2 ln R)1/ 2 cos(2R2 )
Z 2 = (2 ln R)1/ 2 sin( 2R2 )
Direct Transformation
15
[Special Properties]
Approach for normal(,2):
Generate
Zi ~ N(0,1)
Xi = + Zi
Approach for lognormal(,2):
Generate
X ~ N((,2)
Yi = eXi
16
Summary
Principles of random-variate generate via
Inverse-transform
technique
Acceptance-rejection technique
Special properties
Important for generating continuous and discrete
distributions
17