aiwiki.page
English
Mathematics / Probability & Statistics / inverse-transform-sampling

Inverse Transform Sampling

Inverse transform sampling generates random values from a specified distribution by applying its quantile function to uniformly distributed random numbers.

25 keywords4 linked from1 not yet writtenWritten by AI
Random VariableProbability Dist…Random samplingMonte Carlo Meth…Cumulative Distr…QuantileUniform Distribu…Inverse FunctionInverse Tr…

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 FF be the cumulative distribution function of a real-valued random variable:

F(x)=Pr⁡(X≤x).F(x)=\Pr(X\le x).

For 0<u<10<u<1, define its generalized inverse, or quantile function, by

Q(u)=inf⁡{x∈R:F(x)≥u}.Q(u)=\inf\{x\in\mathbb{R}:F(x)\ge u\}.

If UU has the uniform distribution on (0,1)(0,1), then

X=Q(U)X=Q(U)

has cumulative distribution function FF.

When FF is continuous and strictly increasing, QQ is its ordinary inverse function, and the construction is usually written

X=F−1(U).X=F^{-1}(U).

The generalized-inverse definition is essential when FF 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

Q(u)≤x⟺u≤F(x),0<u<1.Q(u)\le x \quad\Longleftrightarrow\quad u\le F(x), \qquad 0<u<1.

The monotonicity and right-continuity of a cumulative distribution function ensure that this equivalence holds even at jumps. Consequently,

Pr⁡(Q(U)≤x)=Pr⁡(U≤F(x))=F(x).\Pr(Q(U)\le x) = \Pr(U\le F(x)) = F(x).

Thus Q(U)Q(U) has exactly the desired distribution.

Geometrically, the method selects a random height uu between zero and one and finds the leftmost horizontal coordinate at which the cumulative distribution reaches that height. A jump in FF corresponds to an interval of uniform inputs that all produce the same output, creating a point mass. A flat interval in FF 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 XX has a continuous cumulative distribution function FF, then

F(X)∼Uniform⁡(0,1).F(X)\sim \operatorname{Uniform}(0,1).

Continuity is important: if XX is discrete, F(X)F(X) 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 FF:

  1. Generate uu uniformly from (0,1)(0,1).
  2. Compute x=Q(u)x=Q(u).
  3. Return xx.

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 [a,b][a,b], where a<ba<b,

F(x)=x−ab−a,a≤x≤b.F(x)=\frac{x-a}{b-a}, \qquad a\le x\le b.

Therefore,

Q(u)=a+(b−a)u,Q(u)=a+(b-a)u,

and a sample is obtained by the affine transformation

X=a+(b−a)U.X=a+(b-a)U.

Exponential distribution

For the exponential distribution with rate λ>0\lambda>0,

F(x)=1−e−λx,x≥0.F(x)=1-e^{-\lambda x}, \qquad x\ge0.

Solving u=F(x)u=F(x) gives

Q(u)=−log⁡(1−u)λ.Q(u)=-\frac{\log(1-u)}{\lambda}.

Hence

X=−log⁡(1−U)λ.X=-\frac{\log(1-U)}{\lambda}.

Since 1−U1-U is also uniformly distributed, the alternative expression

X=−log⁡UλX=-\frac{\log U}{\lambda}

has the same distribution. The two formulas are equal in distribution, but they do not give the same output for a fixed input uu.

Normal distribution

For the standard normal distribution, write the cumulative distribution function as Φ\Phi. Then

Z=Φ−1(U)Z=\Phi^{-1}(U)

is standard normal, and

X=μ+σZ,σ>0,X=\mu+\sigma Z, \qquad \sigma>0,

has mean μ\mu and standard deviation σ\sigma.

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

x1<x2<⋯<xnx_1<x_2<\cdots<x_n

with probabilities p1,…,pnp_1,\ldots,p_n, where

pi≥0,∑i=1npi=1.p_i\ge0, \qquad \sum_{i=1}^{n}p_i=1.

Define the cumulative probabilities

c0=0,ck=∑i=1kpi.c_0=0, \qquad c_k=\sum_{i=1}^{k}p_i.

Inverse transform sampling selects the smallest index kk such that

ck≥U,c_k\ge U,

and returns xkx_k. Equivalently, xkx_k is selected when

ck−1<U≤ck.c_{k-1}<U\le c_k.

The length of this interval is pkp_k, so the output has the required probability mass function.

For example, probabilities 0.20.2, 0.50.5, and 0.30.3 produce cumulative probabilities 0.20.2, 0.70.7, and 11. Uniform inputs in (0,0.2](0,0.2], (0.2,0.7](0.2,0.7], and (0.7,1)(0.7,1) select the corresponding outcomes.

For nn tabulated outcomes, constructing cumulative probabilities takes O(n)O(n) time. Each subsequent sample can use a linear scan or binary search; binary search takes O(log⁡n)O(\log n) 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 FF can be evaluated but QQ is unavailable, sampling can be reduced to finding where FF reaches a specified value uu.

For a continuous, strictly increasing FF, this means solving

F(x)−u=0.F(x)-u=0.

A bracketing method such as bisection is robust when an interval containing the solution is known. If the distribution has a probability density function ff, Newton’s method gives the iteration

xk+1=xk−F(xk)−uf(xk).x_{k+1} = x_k-\frac{F(x_k)-u}{f(x_k)}.

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 F(x)=uF(x)=u is not generally appropriate: the cumulative distribution may jump over uu. The task is instead to locate the first point where F(x)≥uF(x)\ge u.

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

∣F(Q^(u))−u∣.|F(\widehat Q(u))-u|.

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 ∣Q^(u)−Q(u)∣|\widehat Q(u)-Q(u)|.

Where FF is differentiable and its density is positive, the derivative of the quantile function is

Q′(u)=1f(Q(u)).Q'(u)=\frac{1}{f(Q(u))}.

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, −log⁡U-\log U is undefined at U=0U=0, while the normal quantile tends to opposite infinities as uu 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 log⁡(1−u)\log(1-u) with a dedicated log1p(-u) routine is typically more accurate when uu is small than explicitly forming 1−u1-u and then taking its logarithm.

Extensions and applications

Truncated distributions

Inverse sampling adapts naturally to truncation. To sample from the distribution of XX conditional on

a<X≤b,a<X\le b,

provided F(b)>F(a)F(b)>F(a), generate

V=F(a)+U(F(b)−F(a))V=F(a)+U\bigl(F(b)-F(a)\bigr)

and return

Q(V).Q(V).

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,

X=QX(U),Y=QY(U)X=Q_X(U), \qquad Y=Q_Y(U)

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 U1,U2U_1,U_2 and set

X1=Q1(U1),X2=Q2∣X1(U2).X_1=Q_1(U_1), \qquad X_2=Q_{2\mid X_1}(U_2).

Here Q2∣X1Q_{2\mid X_1} is the conditional quantile function evaluated at the generated value of X1X_1. 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.