If we were limited to a random number generator, what technique would you use to generate i.i.d. draws from distribution X?

Question Analysis

The question asks how to generate independent and identically distributed (i.i.d.) samples from a specific probability distribution ( X ) using only a random number generator. This is a common problem in statistics and computer science where you need to simulate random variables from a particular distribution. The challenge lies in the fact that the random number generator typically provides uniform random numbers, and the task is to transform these into random numbers that follow the desired distribution ( X ). Understanding the properties of the distribution ( X ) and the random number generator is crucial to answering this question effectively.

Answer

To generate i.i.d. draws from a distribution ( X ) using a uniform random number generator, you can employ one of several techniques depending on the properties of ( X ):

• Inverse Transform Sampling:

  • Concept: If the cumulative distribution function (CDF) ( F_X ) of the distribution ( X ) is known and invertible, you can use the inverse transform method.
  • Steps:
    1. Generate a uniform random number ( U ) in the range [0, 1].
    2. Compute ( X = F_X^{-1}(U) ).
    3. The value ( X ) is a random sample from the distribution ( X ).

• Rejection Sampling:

  • Concept: Useful when the CDF is not easily invertible or when dealing with complex distributions.
  • Steps:
    1. Choose a proposal distribution ( Y ) that is easy to sample from and satisfies ( \frac{f_X(x)}{c \cdot f_Y(x)} \leq 1 ) for some constant ( c ).
    2. Generate a random sample ( Y ) and a uniform random number ( U ) in [0, 1].
    3. Accept ( Y ) as a sample from ( X ) if ( U \leq \frac{f_X(Y)}{c \cdot f_Y(Y)} ); otherwise, repeat.

• Box-Muller Transform (for Normal Distribution):

  • Concept: Specifically for generating samples from a normal distribution.
  • Steps:
    1. Generate two independent uniform random numbers, ( U_1 ) and ( U_2 ).
    2. Compute ( Z_0 = \sqrt{-2 \ln U_1} \cdot \cos(2\pi U_2) ) and ( Z_1 = \sqrt{-2 \ln U_1} \cdot \sin(2\pi U_2) ).
    3. ( Z_0 ) and ( Z_1 ) are i.i.d. standard normal random variables.

Each method has its own applicability depending on the distribution ( X ) and computational efficiency considerations. The inverse transform method is often intuitive and straightforward if the CDF is invertible, while rejection sampling provides flexibility for more complex distributions.