Week 1

Question 1

What is a Random Number Generator?

Answer 1

A deterministic algorithm that generates numbers U₁, U₂, U₃, …, which appear to be random (independent) numbers from U(0, 1)

Question 2

What are the properties of a RNG?

Answer 2

1. U₁, U₂, … should pass the hypothesis test of being i.i.d. U(0, 1)
2. It should be sufficiently fast, e.g. 1 million numbers within a second
3. You are able to recover the same sequence
4. You are able to get the same numbers on different computers (with same programming language)
5. A good RNG should have a long period

Question 3

What is the Linear congruential random number generator?

Answer 3

• modulus m in {2, 3, 4, …}
• multiplier a in {1, …, m -1}
• increment c in {0, 1, …, m - 1}
• initial value Y₀ in {0, 1, …, m -1}

Then Y_i+1= (aY_i + c), and U_i = Y_i / m

Question 4

What is the Lewis-Goodman-Miller generator?

Answer 4

It’s a Linear Congruential RNG with values:

a = 7⁵ (= 16807)

c = 0

m = 2³¹ - 1 (≈ 2.14 * 10⁹)

Question 5

How to simulate random X using CDF F_X(x)?

Answer 5

1. Simulate U from U(0, 1)
2. X = F_X^-1(U)

Question 6

What are the advantages and disadvantages of the inverse CDF?

Answer 6

Pro:

• Conceptually simple

Cons:

• Only available if F_X^-1 can be derived analytically
• Risc of numerical problems is large
• It is usually to slow

Question 7

How does the Acceptance-rejection method work?

Answer 7

1. Simulate Y from proposal distribution g_Y(y)
2. Simulate U distributed U(0, 1)
3. Check if U ≤ f_X(Y)/(M g_Y(Y)), where M = max_y f_X(y)/g_Y(y)

If yes, X = Y, else reject Y