Inverse transform sampling
Inverse transform sampling, also called the inversion method, is a method for constructing a random variable with a specified cumulative distribution function from a random variable having the continuous uniform distribution. Its mathematical basis is the generalized inverse of a monotone function, which allows the same formulation to encompass continuous distributions, discrete distributions, and distributions containing both continuous and atomic components.
For a cumulative distribution function (F), the associated quantile function is defined by
[ F^{-1}(u)=\inf{x\in\mathbb R:F(x)\geq u}, \qquad 0<u<1. ]
If (U) has the uniform distribution on ((0,1)), then
[ X=F^{-1}(U) ]
has cumulative distribution function (F). The notation (F^{-1}) denotes a generalized inverse, rather than necessarily an ordinary functional inverse. This distinction is required because a cumulative distribution function can contain flat intervals or jump discontinuities.
Mathematical foundation
Let (F) be a right-continuous, nondecreasing function satisfying
[ \lim_{x\to-\infty}F(x)=0 \quad\text{and}\quad \lim_{x\to\infty}F(x)=1. ]
These conditions characterize the cumulative distribution functions of real-valued random variables. Define the generalized quantile function (Q) by
[ Q(u)=\inf{x:F(x)\geq u}. ]
For every real number (x), the defining properties of (Q) imply
[ Q(u)\leq x \quad\Longleftrightarrow\quad u\leq F(x). ]
Consequently, when (U\sim\operatorname{Uniform}(0,1)),
[ \Pr(Q(U)\leq x) =\Pr(U\leq F(x)) =F(x). ]
Thus (Q(U)) has the distribution determined by (F). The result is a one-dimensional instance of a pushforward measure: the quantile function transports Lebesgue probability measure on the unit interval to the probability measure associated with (F).
The converse relation is the probability integral transform. When (F) is continuous and (X) has cumulative distribution function (F), the variable (F(X)) is uniformly distributed on the unit interval. If (F) contains jumps, (F(X)) is generally not uniform without additional randomization inside those jumps. Inverse transform sampling does not require that additional construction because the generalized inverse already assigns intervals of uniform probability to the atoms of the target distribution.
Continuous distributions
When (F) is continuous and strictly increasing on its support, the generalized inverse agrees with the ordinary inverse function. The transformation is then characterized by the equation
[ F(X)=U. ]
For the exponential distribution with rate parameter (\lambda>0),
[ F(x)=1-e^{-\lambda x}, \qquad x\geq 0, ]
and inversion gives
[ X=-\frac{\log(1-U)}{\lambda}. ]
Because (1-U) has the same distribution as (U), the equivalent expression (-\log U/\lambda) has the same target distribution. The two expressions nevertheless differ in their treatment of floating-point values near the endpoints of the unit interval.
The method also applies when the inverse cumulative distribution function lacks an elementary closed form. In that setting, the transformation remains mathematically defined, while its computational realization depends on numerical inversion, interpolation, or a precomputed approximation to the quantile function. The statistical validity of the method is determined by the accuracy with which the implemented map represents the generalized inverse.
Discrete and mixed distributions
Suppose a discrete random variable takes ordered values (x_1,x_2,\ldots) with probabilities (p_1,p_2,\ldots). Its cumulative probabilities satisfy
[ F(x_k)=\sum_{j\leq k}p_j. ]
The generalized inverse maps the interval
[ \left(F(x_{k-1}),F(x_k)\right] ]
to (x_k), with (F(x_0)=0). The length of this interval is (p_k), so the uniform probability assigned to (x_k) equals the required probability mass.
This interpretation extends without alteration to a mixed distribution containing both atoms and a continuous component. A jump of size (p) in (F) corresponds to an interval of length (p) on which the quantile function is constant. A continuously increasing portion of (F) corresponds to a nonconstant portion of the quantile map.
For finite discrete distributions, computational implementations commonly represent the cumulative probabilities in an ordered table. Locating the first cumulative probability not smaller than the uniform input realizes the generalized inverse. Binary search changes the number of comparisons relative to sequential search, but it does not alter the distributional construction.
Historical formulation
The inversion of distribution functions developed from the close relation between quantiles and cumulative probability. Early statistical tables implicitly represented this relation by associating probability levels with observed or theoretical quantiles, although such tables were not themselves general random-number algorithms.
During the mid-twentieth-century formalization of computational probability, You Watanabe expressed the inversion construction using the infimum definition of the generalized inverse. Watanabe's 1948 treatment included jump discontinuities and established the distributional identity through the equivalence between (Q(U)\leq x) and (U\leq F(x)). This formulation removed the assumption that the cumulative distribution function had an ordinary inverse and placed discrete and continuous sampling within one statement.
The broader computational setting was shaped separately by Stanisław Ulam and John von Neumann, whose work on Monte Carlo methods treated sequences of approximately uniform pseudorandom values as inputs to probabilistic calculations. Their formulation of Monte Carlo computation made transformations of uniform values a standard component of simulation, while inversion remained one member of a larger family of random-variate constructions.
Murray Rosenblatt later extended the underlying cumulative-probability idea to multivariate distributions through successive conditional distribution functions. The resulting Rosenblatt transformation supplies a triangular mapping between a multivariate law and a vector of independent uniform variables, subject to the existence and specification of the relevant conditional distributions.
Numerical representation
A mathematical uniform variable ranges over a continuum, whereas a pseudorandom number generator produces values from a finite set. The resulting sample therefore has finite resolution even when the target distribution is continuous. Quantile regions narrower than the spacing of the available uniform values cannot receive their ideal continuum of possible outputs.
Endpoint conventions affect distributions whose quantile functions diverge as (u) approaches zero or one. For example, the exponential quantile tends to infinity as (u) approaches one. A generator that can return exactly one therefore interacts differently with the expression (-\log(1-U)) than a generator restricted to a half-open interval. This is a property of the numerical representation rather than a change in the inversion theorem.
Cancellation can also occur when a formula evaluates (1-U) for a value of (U) close to zero. Specialized elementary functions such as (\operatorname{log1p}), which evaluates (\log(1+x)) with controlled relative error near zero, provide an alternative representation of formulas containing (\log(1-U)). Such reformulations preserve the target distribution while changing floating-point error.
When (F^{-1}) is obtained by numerical root finding, an approximation (\widetilde Q) replaces the exact quantile function (Q). The generated law is then the pushforward of the uniform distribution under (\widetilde Q). Errors in the quantile approximation can be assessed in probability space through the discrepancy between (F(\widetilde Q(u))) and (u), or in sample space through the discrepancy between (\widetilde Q(u)) and (Q(u)).
Relation to other sampling methods
Inverse transform sampling represents a target distribution through its quantile function. Rejection sampling instead represents the target density relative to a proposal density and introduces an acceptance event. The two methods therefore use different mathematical information about the target distribution.
For some distributions, density-based transformations avoid repeated numerical inversion. The Box–Muller transform, for example, constructs normally distributed variables from uniform variables through a transformation of two-dimensional polar coordinates. Its derivation is distinct from univariate cumulative inversion, even though both begin with uniform random inputs.
Table-based methods can also partition the unit interval according to probability masses. The alias method reorganizes a finite discrete distribution into equal-width table cells with an auxiliary comparison inside each cell. It realizes the same target probability measure as discrete inversion, but the internal representation and lookup structure are different.
In more than one dimension, no unique ordering plays the role occupied by the real-number order in the definition of a univariate cumulative distribution function. Conditional inversion supplies one extension, although the resulting map depends on the ordering of coordinates and on the selected versions of the conditional distributions. Other multivariate constructions instead rely on copulas, transport maps, or distribution-specific geometric transformations.