Transcript Communication Systems and Networks

Simulation and Random
Number Generation
Summary


Discrete Time vs Discrete Event Simulation
Random number generation






Generating a random sequence
Generating random variates from a Uniform distribution
Testing the quality of the random number generator
Some probability results
Evaluating integrals using Monte-Carlo simulation
Generating random numbers from various distributions


Generating discrete random variates from a given pmf
Generating continuous random variates from a given
distribution
Discrete Time vs. Discrete Event
Simulation



Solve the finite difference equation
xk 1  min 100, xk  0.1xk 1  log xk  uk 
Given the initial
conditions x0, x-1 and the
input function uk, k=0,1,…
we can simulate the
output!
This is a time driven
simulation.
For the systems we are
interested in, this method
has two main problems.
100
50
0
x(k)

-50
-100
-150
-10
0
10
20
k
30
40
50
Issues with Time-Driven Simulation

System Input
1
u1 (t )  
0
1
u2 (t )  
0
if parcel arrives at t
otherwise
if truck arrives at t
otherwise

System Dynamics
 x(t )  1 if u1 (t )  1, u2 (t )  0,

x(t  )   x(t )  1 if u1 (t )  0, u2 (t )  1
 x(t )
otherwise

u1(t)
t
u2(t)
Δt
t
x(t)
t


Inefficient: At most steps nothing happens
Accuracy: Event order in each interval
Time Driven vs. Event Driven
Simulation Models

Time Driven Dynamics

 x(t )  1 if u1 (t )  1, u2 (t )  0,

x(t  )   x(t )  1 if u1 (t )  0, u2 (t )  1
 x(t )
otherwise


In this case, time is
divided in intervals of
length Δt, and the state is
updated at every step
Event Driven Dynamics
 x  1 if e  a
f  x, e    
 x  1 if e  d

State is updated only at
the occurrence of a
discrete event
Pseudo-Random Number Generation


It is difficult to construct a truly random number generator.
Random number generators consist of a sequence of
deterministically generated numbers that “look” random.




A deterministic sequence can never be truly random.
This property, though seemingly problematic, is actually desirable
because it is possible to reproduce the results of an experiment!
Multiplicative Congruential Method
xk+1 = a xk modulo m
The constants a and m should follow the following criteria



For any initial seed x0, the resultant sequence should look like random
For any initial seed, the period (number of variables that can be
generated before repetition) should be large.
The value can be computed efficiently on a digital computer.
Pseudo-Random Number Generation

To fit the above requirements, m should be chosen
to be a large prime number.



Good choices for parameters are
 m= 231-1 and a=75 for 32-bit word machines
 m= 235-1 and a=55 for 36-bit word machines
Mixed Congruential Method
xk+1 = (a xk + c) modulo m
A more general form:
 n

xk    a j xk  j  mod m
 j 1



where n is a positive constant
xk/m maps the random variates in the interval [0,1)
Quality of the Random Number
Generator (RNG)

The random variate uk=xk/m should be uniformly
distributed in the interval [0,1).
 Divide
the interval [0,1) into k subintervals and count
the number of variates that fall within each interval.
 Run the chi-square test.

The sequence of random variates should be
uncorrelated
 Define
the auto-correlation coefficient with lag k > 0 Ck
and verify that E[Ck] approached 0 for all k=1,2,…
1 nk
1
1
Ck 
u

u




i
i k
2
2
n  k i 1
where ui is the random variate in the interval [0,1).
Some Probability Review/Results

Probability mass functions

Cumulative mass functions
FX  x   Pr  X  x
Pr{X=1}=p1
Pr{X=2}=p2
Pr{X=3}=p3
1

2
3
X
 Pr  X  i  1
i 

x
 Pr  X  i
i 
1
p1+ p 2 + p3
p 1+ p2
p1
1
2
3
X
Some Probability Results/Review

Probability density functions
fX(x)

Cumulative distribution
FX  x   Pr  X  x
x
x1
0
Pr{x=x1}= 0!
x1  
 f
x1 

f X ( y )dy

Pr  x1    X  x1    


x
X
1
FX(x)
 x  dx
0
x
Independence of Random Variables

Joint cumulative probability distribution.
FXY ( x, y)  Pr  X  x, Y  y

Independent Random Variables.
Pr  X  C, Y  D  Pr  X  C Pr Y  D

For discrete variables
Pr  X  x, Y  y  Pr  X  x Pr Y  y

For continuous variables
f XY ( x, y)  f X ( x) fY ( y)
FXY ( x, y)  FX ( x) FY ( y)
Conditional Probability

Conditional probability for two events.
Pr  A | B 

Pr  AB
Pr  B
Bayes’ Rule.
Pr B | A 

Pr  AB
Pr  A
 Pr  A | B 
Pr B | A Pr  A
Pr B
Total Probability
Pr  X  x   Pr  X  x | Y  yk  Pr Y  yk 
k
Expectation and Variance

Expected value of a random variable
EX  

 x Pr{X  x }
i 

i
EX  
 xf
X
( x)dx

Expected value of a function of a random variable
E  g  X  

i


 g  x  Pr{X  x }
i 
i
i
E  g  X  

 g  x f

Variance of a random variable
var  X   E  X  E  X  
2
X
( x)dx
Covariance of two random variables

The covariance between two random variables is defined
as
cov  X , Y   E  X  E  X  Y  E Y 
cov  X , Y   E  XY  XE Y   YE  X   E  X  E Y 
 E  XY   E  X  E Y 

The covariance between two independent random
variables is 0 (why?)
E  XY    xi y j Pr  X  xi , Y  y j 
i
j
  xi Pr  X  xi   y j Pr Y  y j   E  X  E Y 
i
j
Markov Inequality

If the random variable X takes only non-negative values,
then for any value a > 0.
E X 
Pr  X  a 
a

Note that for any value 0<a < E[X], the above inequality
says nothing!
Chebyshev’s Inequality

If X is a random variable having mean μ and variance σ2,
then for any value k > 0.
1
Pr  X    k   2
k
σ
kσ
kσ
fX(x)
μ

x
This may be a very conservative bound!

Note that for X~N(0,σ2), for k=2, from Chebyshev’s inequality Pr{.}<0.25,
when in fact the actual value is Pr{.}< 0.05
The Law of Large Numbers

Weak: Let X1, X2, … be a sequence of independent and
identically distributed random variables having mean μ.
Then, for any ε >0
 X 1  ...  X n

Pr 
      0,
n



Strong: with probability 1,
X1  ...  X n

lim
n
n 
as n  
The Central Limit Theorem

Let X1, X2, …Xn be a sequence of independent random
variables with mean μi and variance σι2. Then, define
the random variable X,
X  X 1  ...  X n

Let
n
  E  X   E  X1  ...  X n    i
n
 2  E  X   2   2
i 1
i 1

Then, the distribution of X approaches the normal
distribution as n increases, and if Xi are continuous, then
f X  x 
1
2
 x    / 2
2
e
Chi-Square Test







Let k be the number of subintervals, thus pi=1/k, i=1,…,k.
Let Ni be the number of samples in each subinterval. Note that
E[Ni]=Npi where N is the total number of samples
Null Hypothesis H0: The probability that the observed random variates
are indeed uniformly distributed in (0,1).
Let T be
2
k
k
1
T
Npi
  Ni  Npi 
i 1
2
k

N
N

N

 i


k


i 1
Define p-value= PH0{T>t} indicate the probability of observing a value t
assuming H0 is correct.
For large N, T is approximated by a chi-square distribution with k-1
degrees of freedom, thus we can use this approximation to evaluate the
p-value
The H0 is accepted if p-value is greater than 0.05 or 0.01
Monte-Carlo Approach to Evaluating
Integrals

Suppose that you want to estimate θ, however it is rather
difficult to analytically evaluate the integral.
1
   g  x  dx
0


Suppose also that you don’t want to
use numerical integration.
Let U be a uniformly distributed random variable in the
interval [0,1) and ui are random variates of the same
distribution. Consider the following estimator.
n
1
ˆ   g  ui   E  g U  as n  
n i 1
1

Also note that:   g  u  du  E  g U 

0
Strong Law of
Large Numbers
Monte-Carlo Approach to Evaluating
Integrals

Use Monte-Carlo simulation to estimate the following
b
integral.
   g  x  dx
a

Let y=(x-a)/(b-a), then the integral becomes
1
1
    b  a  g   b  a  y  a  dy   h  y  dy
0

What if
0

   g  x  dx
0


Use the substitution y= 1/(1+x),
What if
1 1
1
0 0
0
    ... g  x1 ,..., xn  dx1 ...dxn
Example: Estimate the value of π.
(-1,1)
(1,1)
Area of Circle 

Area of square 4
(-1,-1)



(1,-1)
Let X, Y, be independent
random variables uniformly
distributed in the interval [-1,1]
The probability that a point
(X,Y) falls in the circle is given
by

2
2
Pr  X  Y  1 
4
SOLUTION
 Generate N pairs of uniformly distributed random variates (u1,u2) in
the interval [0,1).
 Transform them to become uniform over the interval [-1,1), using
(2u1-1,2u2-1).
 Form the ratio of the number of points that fall in the circle over N
Discrete Random Variates

Suppose we would like to generate a sequence of
discrete random variates according to a probability mass
function
N
Pr  X  x j   p j , j  0,1,..., N ,  p j  1
j 0
1
u
X
Inverse Transform Method
x
 x0
x
 1

X 
x
 j


if u  p0
if p0  u  p0  p1
j 1
if
p
i 0
i
j
 u   pi
i 0
Discrete Random Variate Algorithm
(D-RNG-1)

Algorithm D-RNG-1
 Generate u=U(0,1)
 If u<p0, set X=x0, return;
 If u<p0+p1, set X=x1, return;
…
 Set X=xn, return;

Recall the requirement for efficient implementation, thus
the above search algorithm should be made as efficient
as possible!

Example: Suppose that X{0,1,…,n} and p0= p1 =…= pn
= 1/(n+1), then
X   n  1 u 
Discrete Random Variate Algorithm


Assume p0= 0.1, p1 = 0.2, p2 = 0.4, p3 = 0.3. What is an
efficient RNG?
D-RNG-1: Version 1






Generate u=U(0,1)
If u<0.1, set X=x0, return;
If u<0.3, set X=x1, return;
If u<0.7, set X=x2, return;
Set X=x3, return;
D-RNG-1: Version 2





Generate u=U(0,1)
If u<0.4, set X=x2, return;
If u<0.7, set X=x3, return;
If u<0.9, set X=x1, return;
Set X=x0, return;
More Efficient
Geometric Random Variables

Let p the probability of success and q=1-p the probability
of failure, then X is the time of the first success with pmf
Pr  X  i  pq

i 1
Using the previous discrete random variate algorithm, X=j if
j 1
j
i 1
i 1
 Pr  X  i  U   Pr  X  i
j 1
 Pr  X  i  1  Pr  X  j  1  1  q
j 1
 1  q j 1  U  1  q j
 q j  1  U  q j 1
i 1
 X  min  j : q j  1  U
X  min  j : j log  q   log 1  U 

log 1  U  


 min  j : j 

log
q
  


As a result:
 log 1  U  
X 
1

 log  q  
Poisson and Binomial Distributions

Poisson Distribution with rate λ.
Pr  X  i 


Note:
pi 1 

i 1
i 
e
i!
, i  0,1,...
pi
The binomial distribution (n,p) gives the number of successes
in n trials given that the probability of success is p.
Pr  X  i 

Note: pi 1
n!
i ! n  i  !
n 1 p

pi
i 1 1 p
p i 1  p 
n i
, i  0,1,..., n
Accept/Reject Method (D-RNG-AR)


Suppose that we would like to generate random variates
from a pmf {pj, j≥0} and we have an efficient way to
generate variates from a pmf {qj, j≥0}.
Let a constant c such that
pj
qj


 c for all j such that p j  0
In this case, use the following algorithm
D-RNG-AR:
1.
2.
3.
4.
Generate a random variate Y from pmf {qj, j≥0}.
Generate u=U(0,1)
If u< pY/(cqY), set X=Y and return;
Else repeat from Step 1.
Accept/Reject Method (D-RNG-AR)

Show that the D-RNG-AR algorithm generates a random
variate with the required pmf {pj, j≥0}.
pi  Pr  X  i 

 Pr not stop for 1,...,k 1 Pr  X  i and stop at iteration k
k 1
Pr  X  i and stop after k 
pi
pi
q

Pr  X  i | Y  i and is accepted Pr Y accepted|Y  i Pr Y  i  i
cqi
c
1
pi/cqi
qi


Pr Not stop up to k  1    Pr Y not accepted|Y  j Pr Y  j 
 j

k 1
k 1
 
pj  
 1
1

   
 q j    1  
 j
 c
  cq j  
Therefore

 1
pi   1  
c
k 1 
k 1
pi

c
pi
k 1
D-RNG-AR Example

Determine an algorithm for generating random variates for
a random variable that take values 1,2,..,10 with
probabilities 0.11, 0.12, 0.09, 0.08, 0.12, 0.10, 0.09, 0.09,
0.10, 0.10 respectively.
 pi 
c  max    1.2
i
 qi 

D-RNG-1:




Generate
u=U(0,1)
k=1;
while(u >cdf(k))
 k=k+1;
x(i)=k;

D-RNG-AR:




u1=U(0,1), u2=U(0,1)
Y=floor(10*u1 + 1);
while(u2 > p(Y)/c)
 u1= U(0,1); u2=U(0,1);
 Y=floor(10*rand + 1);
y(i)=Y;
The Composition Approach


Suppose that we have an efficient way to generate
variates from two pmfs {qj, j≥0} and {rj, j≥0}
Suppose that we would like to generate random variates
for a random variable having pmf, a (0,1).
Pr  X  j  p j  aq j  (1  a)rj , j  0

Let X1 have pmf {qj, j≥0} and X2 have pmf {rj, j≥0} and
define
with probability a
X
X  1
X2

with probability 1- a
Algorithm D-RNG-C:



Generate u=U(0,1)
If u <= a generate X1
Else generate X2
Continuous Random Variates
Inverse Transform Method


Suppose we would like to generate a sequence of
continuous random variates having density function FX(x)
Algorithm C-RNG-1: Let U be a random variable uniformly
distributed in the interval (0,1). For any continuous
distribution function, the random variate X is given by
X  FX1 U 
FX(x) 1
u
X
x
Example: Exponentially Distributed
Random Variable

Suppose we would like to generate a sequence of random
variates having density function
f X  x    e  x


Solution
Find the cumulative distribution
x
FX  x     e  y dy  1  e   x
0

Let a uniformly distributed random variable u
u  FX  x   1  e

 x
1
 ln 1  u    x  x   ln 1  u 

Equivalently, since 1-u is also uniformly distributed in (0,1)
1
x   ln  u 

Convolution Techniques and the Erlang
Distribution

Suppose the random variable X is the sum of a number of
independent identically distributed random variables
n
X  Yi
i 1

Algorithm C-RNG-Cv:



Generate Y1,…,Yn from the given distribution
X=Y1+Y2+…+Yn.
An example of such random variable is the Erlang with
order n which is the sum of n iid exponential random
variables with rate λ.
  x n e  x
f X ( x) 
n!
Accept/Reject Method (C-RNG-AR)

Suppose that we would like to generate random variates
from a pdf fX(x) and we have an efficient way to generate
variates from a pdf gX(x).
Let a constant c such that

In this case, use the following algorithm


fX  x
 c for all x
gX  x
C-RNG-AR:
1.
2.
3.
4.
Generate a random variate Y from density gX(x).
Generate u=U(0,1)
If u< fX(Y)/(cgX(Y)), set X=Y and return;
Else repeat from Step 1.
Accept/Reject Method (C-RNG-AR)

The C-RNG-AR is similar to the D-RNG-AR algorithm
except the comparison step where rather than comparing
the two probabilities we compare the values of the density
functions.

Theorem



The random variates generated by the Accept/Reject method
have density fX(x).
The number of iterations of the algorithm that are needed is a
geometric random variable with mean c
Note: The constant c is important since is implies the number of
iterations needed before a number is accepted, therefore it is required
that it is selected so that it has its minimum value.
C-RNG-AR Example


Use the C-RNG-AR method to generate random variates
X that are normally distributed with mean 0 and variance
1, N(0,1).
First consider the pdf of the absolute value of |X|.
f| X | ( x ) 

2
2
e
 12 x2
We know how to generate exponentially distributed
random variates Y with rate λ=1.
gY ( x)  e x , x  0

Determine c such that it is equal to the maximum of the ratio
f| X | ( x )
2 x  12 x2
2e

e
c
gY  x 
2

C-RNG-AR Example

C-RNG-AR for N(0,1):







u1=U(0,1), u2=U(0,1);
Y= -log(u1);
while(u2 > exp(-0.5(Y-1)*(Y-1)))
 u1= U(0,1); u2=U(0,1);
 Y= -log(u1);
u3= U(0,1);
If u3 < 0.5 X=Y;
Else X= -Y;
Suppose we would like Z~N(μ, σ2), then
Z :  X  
Generating a Homogeneous Poisson
Processes

A homogenous Poisson process is a sequence of points
(events) where the inter-even times are exponentially
distributed with rate λ (The Poisson process will be studied in detail during
later classes)


Let ti denote the ith point of a Poisson process, then the
algorithm for generating the first N points of the sequence
{ti, i=1,2,…,N} is given by
Algorithm Poisson-λ:



k=0, t(k)=0;
While k<N
 k= k+1;
 Generate u=U(0,1)
 t(k)= t(k-1) – log(u)/lambda;
Return t.
Generating a Non-Homogeneous
Poisson Processes



Suppose that the process is non-homogeneous i.e., the
rate varies with time, i.e., λ(t) ≤λ, for all t<T.
Let ti denote the ith point of a Poisson process, and τ the
actual time, then the algorithm for generating the first N
points of the sequence {ti, i=1,2,…,N} is given by
Algorithm Thinning Poisson-λ:


k=0, t(k)=0, tau= 0;
While k<N
 Generate u1=U(0,1);
 tau= tau – log(u1)/lambda;
 Generate u2= U(0,1);
 If(lambda(tau)\lambda < u2)


k= k+1, t(k)= tau;
Return t.
Generating a Non-Homogeneous
Poisson Processes


Again, suppose that the process is non-homogeneous
i.e., the rate varies with time, i.e., λ(t) ≤λ, for all t<T but
now we would like to generate all points ti directly, without
thinning.
Assuming that we are at point ti, then the question that we
need to answer is what is the cdf of Si where Si is the time
until the next event


F|Si | (s)  Pr Si  s | t  ti   1  exp     ti  y  dy

s
0
Thus, to simulate this process, we start from t0 and
generate S1 from FS1 to go to t1=t0+S1. Then, from t1, we
generate S2 from FS2 to go to t2=t1+S2 and so on.
Example of Non-Homogeneous
Poisson Processes

Suppose that λ(t)= 1/(t+α), t ≥0, for some positive constant
a. Generate variates from this non-homogeneous
Poisson process.

First, let us determine the rate of the cdf
 s  ti  a 
1
0   ti  y  dy  0  a  ti  y  dy  log  ti  a 
ti  a
s

 s  ti  a  
FSi  1  exp  log 
  1 s  t  a  s  t  a

i
i
 ti  a  

s

s
Inverting this yields
1
FS 
i
ti  a  u
1 u
Example of Non-Homogeneous
Poisson Processes

Inverse Transform
1
FS 
i

ti  a  u
1 u
Thus we start from t0=0
t1  t0 
 t0  a  u1
t2  t1 
1  u1
au1

1  u1
1  u2
t1  au2

1  u2
 t1  a  u2
…
ti  ti 1 
 ti 1  a  ui
1  ui
ti 1  aui

1  ui
The Composition Approach


Suppose that we have an efficient way to generate
variates from cdfs G1(x),…, Gn(x).
Suppose that we would like to generate random variates
for a random variable having cdf
n
FX  x    rG
( x),
i
i
i 1

n
 r  1,
i 1
i
ri  0, i  1,..., n
Algorithm C-RNG-C:

Generate u=U(0,1)
 If
u<p1, get X from G1(x), return;
 If u<p1+p2, get X from G2(x), return;
…
Polar Method for Generating Normal
Random Variates

Let X and Y be independent normally distributed random
variables with zero mean and variance 1. Then the joint
density function is given by
1  12 x2 1  12 y2
1  12  x2  y2 
f XY ( x, y) 
2

Y
e
2
rx y

θ
X
2
e
Then make a variable change
2
R

e
2
y
  arctan
x
The new joint density function is
1 1  12 r
f R (r, ) 
e
2 2
Uniform in the
interval [0,2π]
Exponential
with rate 1/2
Polar Method for Generating Normal
Random Variates

Algorithm C-RNG-N1:





Generate u1=U(0,1), u2=U(0,1);
R= -2*log(u1); W= 2*pi*u2;
X= sqrt(R) cos(W); Y= sqrt(R) sin(W);
Generates 2
independent
RVs
But, sine and cosine evaluations are inefficient!
Algorithm C-RNG-N2:
1.
2.
3.
4.
5.
6.
7.
Generate u1=U(0,1), u2=U(0,1);
Set V1= 2*u1-1, V2= 2*u2-1; (-1,1)
S=V1*V1+V2*V2;
If S > 1, Go to 1
R= sqrt(-2*log(S)/S);
X= R*V1;
Y= R*V2;
(-1,-1)
(1,1)
(V1,V2)
(1,-1)
Simulation of Discrete Event Systems
INITIALIZE
TIME
STATE
CLOCK
STRUCTURE
RNG
…
Update State
x’=f(x,e1)
EVENT CALENDAR
e1
t1
e2
t2
Delete
Infeasible
Events
Add New
Feasible
Events
Update Time
t’=t1
Verification of a Simulation Program

Standard debugging techniques
 Debug
“modules” or subroutines
 Create simple special cases, where you know what to
expect as an output from each of the modules
 Often choosing carefully the system parameters, the
simulation model can be evaluated analytically.
 Create a trace which keeps track of the state
variables, the event list and other variables.