Week 3

Question 1

Linear Congruential Generator (LCG)

Definition and Formula

Answer 1

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)

Question 2

Full Period Theorem

Answer 2

A full period is when the period is equal to m

The LCG has a full period <=>

1. c and m are relatively prime (no common divisor except 1)
2. a-1 divisible by all prime factors of m
3. a-1 divisible by 4 if m divisible by 4

Question 3

Requirements of a “Good” Random Number Generator (RNG)

Answer 3

1. Uniformity: appear UNIF[0,1] -> check with histogram
2. Independence -> check with a scatterplot
3. Full period

Question 4

Algorithm for Simulating Homogenous Poisson Process

Answer 4

Algorithm for simulating T time units of a Poisson process
I = # of events
S(I) = event time (in increasing order)

1. Initialize t=0, I=0
2. Generate U~U(0,1)
3. Set t = t - lnU/λ ; if t>T stop
4. Update I = I + 1 , S(I) = t
5. Go to (2)

Question 5

Thinning Algorithm

For Non-Homogenous Poisson Process

Answer 5

1. Initialize t=0, I=0
2. Generate U(1) ~ U(0,1)
3. Set t = t - lnU(1)/λmax , if t>T stop
4. Generate U(2) ~ U(0,1)
5. If U(2) ≤ λ(t)/λmax , set I=I+1 , S(I) = t
6. Go to step 2

Question 6

Batch Arrivals

Answer 6

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)):

1. Generate the next arrival time t(i) from the Poisson process
2. Generate B(i) independently
3. Return with the info. that there are B(i) events at time t(i)

Question 7

Steps for Continuous Inverse Transform Method

Answer 7

1. Compute the CDF of X
2. Set F(X) = U on range of X
3. Solve F(X) = U for X
4. Generate uniform random numbers U(1), U(2), …
5. Compute desired r.v. by X(i) = F^(-1)(U(i))

Question 8

Algorithm for Discrete Inverse Transform Method

Answer 8

1. Generate U~U(0,1)
2. Find the smallest positive integer I s.t. U≤F(X(I))
3. Return X=X(I)

Like how you coded the CDF in Assignment 2