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

In this question, you are asked to generate independent and identically distributed (i.i.d.) samples from a given distribution ( X ), but you are restricted to using a random number generator (RNG). The question is essentially about simulating random samples from a specific probability distribution using a random number generator that typically provides uniformly distributed numbers.

To solve this, you need to select an appropriate method or algorithm that converts uniform random numbers into samples from the desired distribution ( X ). This requires some understanding of probability distributions and simulation techniques. Key techniques include the Inverse Transform Sampling, Rejection Sampling, or other specialized methods depending on the characteristics of the distribution ( X ).

Answer

To generate i.i.d. samples from a distribution ( X ) using a random number generator, you can employ one of the following techniques, depending on the characteristics of the distribution:

1. Inverse Transform Sampling:

   • This technique is suitable when you know the cumulative distribution function (CDF) ( F(x) ) of the distribution ( X ).
   • Steps:
     • Generate a uniform random number ( u ) in the range [0, 1].
     • Compute the inverse of the CDF: ( x = F^{-1}(u) ).
     • The value ( x ) is a sample from the distribution ( X ).

2. Rejection Sampling:

   • Useful when the probability density function (PDF) of the distribution ( X ) is known and can be bounded by another distribution from which we can easily sample.
   • Steps:
     • Choose a proposal distribution ( q(x) ) such that ( q(x) ) is easy to sample from, and there exists a constant ( c ) where ( p(x) \leq c \cdot q(x) ) for all ( x ).
     • Repeat until acceptance:
       • Sample ( x ) from ( q(x) ).
       • Generate a uniform random number ( u ) in the range [0, 1].
       • Accept ( x ) if ( u \leq p(x) / (c \cdot q(x)) ).

3. Use of Specialized Algorithms:

   • For certain distributions like normal, binomial, or others, there are specialized algorithms (e.g., Box-Muller for normal distribution, or Ziggurat algorithm) that can efficiently generate samples.

Conclusion: Choose the method based on the availability of the CDF or PDF of distribution ( X ) and the computational efficiency required for your application.