Week 4

Question 1

Composition Method Idea

Answer 1

We have probabilities of different distributions

F(x) = p(1)F1(x) + p(2)F2(x) + …

When to use: want to generate CDF of F, but inverse transformation is difficult or slow

Question 2

Composition Method Algorithm

Answer 2

1. Generate a discrete random variable I defined so that P(I=i) = p(i) for i=1,2,…
2. Generate a random variable X from the cdf FI(x)
   (The X returned by the algorithm will have distribution F(x))

Example:
1. Generate U1~U(0,1)
2. Generate U2~U(0,1)
3. If U1 < 0.5, set X = -(1/λ1)ln(U2)
    Otherwise, set X = -(1/λ2)ln(U2)

Question 3

Inverse Transform Method

Answer 3

You are given an f(x)
Compute F(x)
Compute inverse of F(x) s.t. we have equation for X in terms of U
Generate U~U(0,1)
If U<0.5 (or whatever probability it is), return X = …
Otherwise, return X = …

Question 4

Composition Method Method

Answer 4

Decompose f(x) - define an indicator function
Compute each F(x)
Compute the inverse of F to get X in terms of U

Question 5

When Can We Not Use the Inverse-Transform or Composition Method?

Answer 5

When there is no closed form for F(x)

Question 6

Continuous Acceptance Rejection Method Idea

Answer 6

Generate a random variable Y from an easy distribution and use a rule to decide whether to accept it as a sample of X or not

Question 7

What is a suitable easy distribution [r(x)] for the Continuous Acceptance-Rejection Method?

Answer 7

It is on the same interval as f(x)

Simple to generate from (e.g. via inverse transform method)

Question 8

Acceptance-Rejection Algorithm

Answer 8

Requirements:

• r(x) > 0 <=> f(x) > 0 for all x
• c is a constant s.t. f(x) ≤ cr(x) for all x

Algorithm:

1. Generate U1~U(0,1) and use this number to generate Y which has density r(x)
2. Generate U2~U(0,1) (independent of U1)
3. If U2

Question 9

Continuous Acceptance-Rejection Theorem

Answer 9

i) The random variable generated by the rejection method has density f
ii) The number of iterations of the algorithm that are needed is a random variable with mean c
- The acceptance probability is 1/c
P{U ≤ f(Y)/cr(Y)} = 1/c

Question 10

How to find constant c in Acceptance-Rejection Method?

Answer 10

We want smallest c s.t. f(x) ≤ cr(x) because we want to maximize acceptance probability

c = max { f(x)/r(x) }
Take derivative w.r.t. x and set equal to 0 to find c

Question 11

Majorizing Function

Answer 11

t(x) = cr(x)

Question 12

Discrete Acceptance-Rejection Method Algorithm

Answer 12

Goal: Generate random variable P with prob. mass function pj
We have efficient method for generating random variable Q with prob. mass function qj

Requirements:

• For all j, qj > 0 <=> pj > 0 (P and Q take on the same set of values)
• c is a constant s.t. pj ≤ cqj for all j

Algorithm:
1. Generate U1~U(0,1) and use this number to generate Y which has probability mass function qj
2. Generate U2~U(0,1) (independent of U1)
3. If U2 ≤ py/cqy, set X=Y and stop (y is subscript)
Otherwise, return to step 1

Question 13

Convolution Method

Answer 13

It is a sum of IDD random variables

Algorithm:

1. Generate Y1, Y2, …, Ym independently from their distribution
2. Return X = Y1 + Y2 + … + Ym (m-fold convolution of the distribution of Yj)

Question 14

Composition vs. Convolution

Answer 14

Composition: Expresses distribution function as weigher sum of other distribution functions
F(x) = p1F1(x) + p2F2(x) + …

Convolution: Expresses the random variable itself as a sum of other random variables
X = Y1 + Y2 + … + Ym