Inverse transform sampling is a method of generating a random variable with a specified probability distribution by applying that distribution’s quantile function to a uniformly distributed random number. It works for continuous, discrete, and mixed distributions when the inverse is interpreted appropriately. The method is a basic tool in random sampling and Monte Carlo methods, both as a practical algorithm and as a mathematical construction showing how arbitrary real-valued distributions can be obtained from uniform randomness.
Mathematical definition
Let be the cumulative distribution function of a real-valued random variable:
For , define its generalized inverse, or quantile function, by
If has the uniform distribution on , then
has cumulative distribution function .
When is continuous and strictly increasing, is its ordinary inverse function, and the construction is usually written
The generalized-inverse definition is essential when has jumps or flat portions. Such functions need not have ordinary inverses, but they still define valid probability distributions.
Why the method works
The central identity is
The monotonicity and right-continuity of a cumulative distribution function ensure that this equivalence holds even at jumps. Consequently,
Thus has exactly the desired distribution.
Geometrically, the method selects a random height between zero and one and finds the leftmost horizontal coordinate at which the cumulative distribution reaches that height. A jump in corresponds to an interval of uniform inputs that all produce the same output, creating a point mass. A flat interval in corresponds to a gap that the generated variable crosses without taking values in its interior.
Relationship to the probability integral transform
The probability integral transform proceeds in the opposite direction. If has a continuous cumulative distribution function , then
Continuity is important: if is discrete, is generally not uniform. Inverse transform sampling, by contrast, remains valid for discrete distributions because it uses the generalized inverse.
Basic algorithm
For a target distribution with cumulative distribution function :
- Generate uniformly from .
- Compute .
- Return .
Repeating this procedure with independent uniform inputs produces independent samples from the target distribution. Applying the same deterministic function separately to each input preserves statistical independence; it does not create independence if the inputs are dependent.
The practical cost depends primarily on how the quantile function is evaluated. Some distributions have simple inverse formulas. Others require numerical approximation or a search through cumulative probabilities.
Continuous examples
Uniform distribution on an interval
For a uniform distribution on , where ,
Therefore,
and a sample is obtained by the affine transformation
Exponential distribution
For the exponential distribution with rate ,
Solving gives
Hence
Since is also uniformly distributed, the alternative expression
has the same distribution. The two formulas are equal in distribution, but they do not give the same output for a fixed input .
Normal distribution
For the standard normal distribution, write the cumulative distribution function as . Then
is standard normal, and
has mean and standard deviation .
The normal quantile function has no elementary closed-form expression. Practical implementations use numerical approximations, often with different formulas for the central region and the tails.
Discrete distributions
Suppose a distribution takes ordered values
with probabilities , where
Define the cumulative probabilities
Inverse transform sampling selects the smallest index such that
and returns . Equivalently, is selected when
The length of this interval is , so the output has the required probability mass function.
For example, probabilities , , and produce cumulative probabilities , , and . Uniform inputs in , , and select the corresponding outcomes.
For tabulated outcomes, constructing cumulative probabilities takes time. Each subsequent sample can use a linear scan or binary search; binary search takes comparisons. These bounds use big O notation and assume the cumulative table is already available.
The same principle applies to countably infinite distributions, such as the Poisson distribution, although searching through many cumulative probabilities may be expensive.
Numerical implementation
Numerical inversion
When can be evaluated but is unavailable, sampling can be reduced to finding where reaches a specified value .
For a continuous, strictly increasing , this means solving
A bracketing method such as bisection is robust when an interval containing the solution is known. If the distribution has a probability density function , Newton’s method gives the iteration
Newton’s method can converge rapidly, but may fail when the initial value is poor, the density is small, or an iteration leaves the support. Safeguarded implementations combine fast iterations with a maintained bracket.
For discontinuous distributions, solving the equality is not generally appropriate: the cumulative distribution may jump over . The task is instead to locate the first point where .
Approximation and interpolation
For repeated sampling, a quantile function may be approximated using tables, piecewise polynomials, or interpolation. The approximation should preserve monotonicity and account for tail behavior.
A useful measure of inversion error is the probability-scale residual
For continuous distributions, this describes how closely the approximate output corresponds to its intended cumulative probability. It is not the same as the value error .
Where is differentiable and its density is positive, the derivative of the quantile function is
Consequently, small errors in probability can produce large errors in the sampled value where the density is small, especially in the tails.
Finite precision and endpoints
An ideal continuous uniform variable equals neither zero nor one with positive probability. Computer-generated uniforms, however, lie on a finite grid whose endpoint convention depends on the implementation.
Endpoint handling matters because quantile functions may be infinite there. For example, is undefined at , while the normal quantile tends to opposite infinities as approaches zero or one.
Floating-point arithmetic also limits the probabilities and tail values that can be represented. A finite grid of uniform inputs cannot reproduce an unbounded continuous distribution exactly.
Numerical stability matters even when an inverse formula is available. For the exponential inverse, evaluating with a dedicated log1p(-u) routine is typically more accurate when is small than explicitly forming and then taking its logarithm.
Extensions and applications
Truncated distributions
Inverse sampling adapts naturally to truncation. To sample from the distribution of conditional on
provided , generate
and return
This restricts the uniform draw to the cumulative-probability interval corresponding to the conditioning event. Different inclusion conventions at the boundaries require care when the original distribution has point masses.
Coupled simulation
Using one uniform variable with several quantile functions produces dependent samples with prescribed marginal distributions. For example,
couples both outputs monotonically to the same input.
Such constructions are useful for comparing simulated systems and for establishing stochastic-ordering results. Using shared random inputs may reduce the variance of a simulated difference, but variance reduction depends on the quantities being compared and is not automatic.
Multivariate sampling
A joint probability distribution generally cannot be sampled by independently applying each marginal quantile function: that would discard its dependence structure.
An extension uses successive conditional distributions. For a bivariate distribution, one may generate independent uniforms and set
Here is the conditional quantile function evaluated at the generated value of . The construction extends to more variables, but computing the required conditional distributions may be difficult.
Advantages and limitations
Inverse transform sampling has a direct mathematical justification, works with arbitrary real-valued distributions, and uses one uniform input per univariate output in its basic form. Its monotone mapping is particularly useful when the relationship between inputs and outputs matters, rather than only the output distribution.
Its main limitation is computational: evaluating the quantile function may be substantially harder than evaluating a density or cumulative distribution. Repeated numerical inversion can be expensive, discrete searches can be slow for large supports, and accurate tail sampling requires careful numerical design.
Alternative methods, including rejection sampling and specialized distribution-specific algorithms, may be faster when inversion is difficult. Their relative efficiency depends on the distribution, required accuracy, preprocessing cost, and number of samples.