Inverse transform sampling can be used to transform samples from the uniform distribution to another by inverting the target distribution’s CDF (a.k.a. computing the quantile function). It is one of the most important techniques to generate samples from a distribution.
The Algorithm
- Compute the CDF1
. - Compute the inverse
. - Obtain a uniformly distributed random number
- Compute
.
Derivation
For a distribution
Substitute
For the canonical uniform distribution,
Intuition
A Discrete Example
We will use a discrete example for demonstration purpose. To draw a sample from the distribution, we need to take a sample
from the canonical uniform random variable and use it to select one of the outcomes in CDF s.t. the probability of choosing that outcome is equal to the probability of the outcome itself. From the CDF, we can see that we generated the y axis (from uniform random variable) of a CDF and we want to map it to the x-axis.
To generalize this example to continuous distribution, consider a discrete distribution where the number of outcomes approach infinity.
Footnotes
-
Assuming the PDF
is zero for . Otherwise we need to integrate from ↩