Linear Congruential Generator (LCG)
Definition and Formula
Definition: Arithmetic generator that creates random numbers U(i); it is the most common random number generator (RNG)
Z(i+1) = (αZ(i) + c) mod m U(i+1) = Z(i+1)/m
Z(0) is the see
m = modulus
α = multiplier
c = shift (increment)
Full Period Theorem
A full period is when the period is equal to m
The LCG has a full period <=>
- c and m are relatively prime (no common divisor except 1)
- a-1 divisible by all prime factors of m
- a-1 divisible by 4 if m divisible by 4
Requirements of a “Good” Random Number Generator (RNG)
- Uniformity: appear UNIF[0,1] -> check with histogram
- Independence -> check with a scatterplot
- Full period
Algorithm for Simulating Homogenous Poisson Process
Algorithm for simulating T time units of a Poisson process
I = # of events
S(I) = event time (in increasing order)
- Initialize t=0, I=0
- Generate U~U(0,1)
- Set t = t - lnU/λ ; if t>T stop
- Update I = I + 1 , S(I) = t
- Go to (2)
Thinning Algorithm
For Non-Homogenous Poisson Process
- Initialize t=0, I=0
- Generate U(1) ~ U(0,1)
- Set t = t - lnU(1)/λmax , if t>T stop
- Generate U(2) ~ U(0,1)
- If U(2) ≤ λ(t)/λmax , set I=I+1 , S(I) = t
- Go to step 2
Batch Arrivals
At t(i) have B(i) events - B(i) is discrete r.v. IDD and independent of t(i)
Algorithm (get t(i) from t(i-1)):
- Generate the next arrival time t(i) from the Poisson process
- Generate B(i) independently
- Return with the info. that there are B(i) events at time t(i)
Steps for Continuous Inverse Transform Method
- Compute the CDF of X
- Set F(X) = U on range of X
- Solve F(X) = U for X
- Generate uniform random numbers U(1), U(2), …
- Compute desired r.v. by X(i) = F^(-1)(U(i))
Algorithm for Discrete Inverse Transform Method
- Generate U~U(0,1)
- Find the smallest positive integer I s.t. U≤F(X(I))
- Return X=X(I)
Like how you coded the CDF in Assignment 2
