Given we only have a random number generator, how could you generate i.i.d. draws from a specific distribution X?

Question Analysis

The question is asking about generating independent and identically distributed (i.i.d.) samples from a specific distribution ( X ) using only a random number generator. This is a common problem in probabilistic programming and computational statistics. The random number generator typically provides uniform random numbers, and the challenge is to transform these uniform samples into samples from the desired distribution.

Key points to consider:

• i.i.d. samples: These are samples that are statistically independent and identically distributed, meaning each sample has the same probability distribution as the others and all are mutually independent.
• Specific distribution ( X ): This could be any known probability distribution (e.g., normal, exponential, binomial, etc.).
• Random number generator: Usually assumed to provide uniform random numbers between 0 and 1. The task is to convert these into samples from ( X ).

Answer

To generate i.i.d. samples from a specific distribution ( X ) using a uniform random number generator, you can follow these steps:

1. Inverse Transform Sampling:

   • This technique involves using the cumulative distribution function (CDF) of the target distribution ( X ). If ( F_X ) is the CDF of ( X ), then:
     [
     X = F_X^{-1}(U)
     ]
     where ( U ) is a uniform random variable between 0 and 1. The function ( F_X^{-1} ) is the inverse CDF, also known as the quantile function.
   • Steps:
     • Generate a uniform random number ( U ) using the random number generator.
     • Compute ( X = F_X^{-1}(U) ) to get a sample from the distribution ( X ).

2. Acceptance-Rejection Method:

   • This method can be used when the inverse CDF is difficult to compute. It involves generating samples from an easier distribution and using a rejection criterion to ensure the samples follow the desired distribution.
   • Steps:
     • Generate a candidate sample ( Y ) from a proposal distribution ( g(y) ) that is easy to sample from.
     • Generate a uniform random number ( U ) between 0 and 1.
     • If ( U \leq \frac{f(y)}{Mg(y)} ), accept ( Y ) as a sample from ( X ). Otherwise, reject it and repeat.
     • Here, ( f(y) ) is the probability density function (PDF) of the target distribution ( X ), and ( M ) is a constant such that ( M \cdot g(y) \geq f(y) ) for all ( y ).

3. Other Methods:

   • Depending on the distribution, other methods like Box-Muller transform (for normal distribution), or using library functions in programming languages (e.g., NumPy in Python) could be employed.

By following these methods, you can successfully generate i.i.d. samples from a given distribution using a basic random number generator.