Inverse Transform Sampling

Inverse transform sampling generates a draw from a target distribution by evaluating the inverse of its cumulative distribution function at a uniform random number, turning a uniform variate into an exact sample.

Definition

Inverse transform sampling is the technique of drawing U uniformly on (0,1) and returning the value at which the cumulative distribution function of the target equals U, thereby producing an exact sample from that distribution.

Scope

This topic covers the probability integral transform that justifies the method, its application to continuous and discrete distributions, the use of numerical inversion when the inverse cumulative distribution function lacks a closed form, and the method's strengths and limitations relative to acceptance-rejection and specialized algorithms.

Core questions

• Why does applying the inverse cumulative distribution function to a uniform variate yield the target distribution?
• How is the method adapted to discrete distributions through the generalized inverse?
• What numerical techniques invert a cumulative distribution function that has no closed form?
• When is inversion preferable to acceptance-rejection or distribution-specific algorithms?

Key concepts

• Cumulative distribution function
• Quantile function
• Probability integral transform
• Numerical inversion
• Monotonicity

Key theories

Probability integral transform

If X has continuous cumulative distribution function F, then F(X) is uniform on (0,1); conversely the inverse of F applied to a uniform variate has distribution F, which is the exact basis of inversion.

Generalized inverse for discrete and mixed distributions

When F is not strictly increasing, the quantile function defined as the infimum of values whose cumulative probability reaches U extends inversion to discrete and mixed distributions, reducing sampling to a search through the cumulative probabilities.

Clinical relevance

Inversion is the workhorse for generating exponential, Cauchy, logistic and many other variates, for simulating from empirical and fitted distributions, and for coupling simulations to common random numbers; because a single uniform input maps to a single output it also enables variance-reduction schemes built on shared randomness.

History

The probability integral transform was established in early twentieth-century mathematical statistics and became a standard simulation tool once digital computers made evaluating quantile functions routine, with later emphasis on accurate numerical inversion for distributions lacking closed-form quantiles.

Key figures

• Luc Devroye
• Christian P. Robert
• George Casella

Seminal works

• devroye1986
• robert2004

Frequently asked questions

When can inverse transform sampling not be used directly?

It requires evaluating the inverse cumulative distribution function. For distributions such as the normal, whose inverse has no elementary closed form, one uses accurate numerical approximations or switches to another method like acceptance-rejection.

Does inversion work for discrete distributions?

Yes. Using the generalized inverse, one returns the smallest value whose cumulative probability is at least the uniform draw, which amounts to searching the table of cumulative probabilities for the target.