Inverse transform sampling (also known asinversion sampling, theinverse probability integral transform, theinverse transformation method, or theSmirnov transform) is a basic method forpseudo-random number sampling, i.e., for generating sample numbers atrandom from anyprobability distribution given itscumulative distribution function.

Inverse transformation sampling takesuniform samples of a number${\displaystyle u}$ between 0 and 1, interpreted as a probability, and then returns the smallest number${\displaystyle x\in \mathbb{R}}$ such that${\displaystyle F(x)\ge u}$ for thecumulative distribution function${\displaystyle F}$ of a random variable. For example, imagine that${\displaystyle F}$ is the standardnormal distribution with mean zero andstandard deviation one. The table below shows samples taken from the uniform distribution and their representation on the standard normal distribution.

Transformation from uniform sample to normal

${\displaystyle u}$	${\displaystyle F^{-1}(u)}$
.5	0
.975	1.95996
.995	2.5758
.999999	4.75342
1-2−52	8.12589

We are randomly choosing a proportion of the area under the curve and returning the number in the domain such that exactly this proportion of the area occurs to the left of that number. Intuitively, we are unlikely to choose a number in the far end of tails because there is very little area in them which would require choosing a number very close to zero or one.

Computationally, this method involves computing thequantile function of the distribution — in other words, computing thecumulative distribution function (CDF) of the distribution (which maps a number in the domain to a probability between 0 and 1) and theninverting that function. This is the source of the term "inverse" or "inversion" in most of the names for this method. Note that for adiscrete distribution, computing the CDF is not in general too difficult: we simply add up the individual probabilities for the various points of the distribution. For acontinuous distribution, however, we need to integrate theprobability density function (PDF) of the distribution, which is impossible to do analytically for most distributions (including thenormal distribution). As a result, this method may be computationally inefficient for many distributions and other methods are preferred; however, it is a useful method for building more generally applicable samplers such as those based onrejection sampling.

For thenormal distribution, the lack of ananalytical expression for the corresponding quantile function means that other methods (e.g. theBox–Muller transform) may be preferred computationally. It is often the case that, even for simple distributions, the inverse transform sampling method can be improved on:^[1] see, for example, theziggurat algorithm andrejection sampling. On the other hand, it is possible to approximate the quantile function of the normal distribution extremely accurately using moderate-degree polynomials, and in fact the method of doing this is fast enough that inversion sampling is now the default method for sampling from a normal distribution in the statistical packageR.^[2]

For anyrandom variable${\displaystyle X\in \mathbb{R}}$, the random variable${\displaystyle F_X^{-1}(U)}$ has the same distribution as${\displaystyle X}$, where${\displaystyle F_X^{-1}}$ is thegeneralized inverse of thecumulative distribution function${\displaystyle F_X}$ of${\displaystyle X}$ and${\displaystyle U}$ is uniform on${\displaystyle [0,1]}$.^[3]

Forcontinuous random variables, theinverse probability integral transform is indeed the inverse of theprobability integral transform, which states that for acontinuous random variable${\displaystyle X}$ withcumulative distribution function${\displaystyle F_X}$, the random variable${\displaystyle U=F_X(X)}$ isuniform on${\displaystyle [0,1]}$.

From${\displaystyle U\sim \mathrm{U}\mathrm{n}\mathrm{i}\mathrm{f}[0,1]}$, we want to generate${\displaystyle X}$ withCDF${\displaystyle F_X(x).}$ We assume${\displaystyle F_X(x)}$ to be a continuous, strictlyincreasing function, which provides good intuition.

We want to see if we can find some strictly monotone transformation${\displaystyle T:[0,1]\mapsto \mathbb{R}}$, such that${\displaystyle T(U)\stackrel{d}{=}X}$. We will have

${\displaystyle F_X(x)=Pr(X\le x)=Pr(T(U)\le x)=Pr(U\le T^{-1}(x))=T^{-1}(x),\text{ for }x\in \mathbb{R},}$

where the last step used that${\displaystyle Pr(U\le y)=y}$ when${\displaystyle U}$ is uniform on${\displaystyle [0,1]}$.

So we got${\displaystyle F_X}$ to be the inverse function of${\displaystyle T}$, or, equivalently${\displaystyle T(u)=F_X^{-1}(u),u\in [0,1].}$

Therefore, we can generate${\displaystyle X}$ from${\displaystyle F_X^{-1}(U).}$

The problem that the inverse transform sampling method solves is as follows:

• Let${\displaystyle X}$ be arandom variable whose distribution can be described by thecumulative distribution function${\displaystyle F_X}$.
• We want to generate values of${\displaystyle X}$ which are distributed according to this distribution.

The inverse transform sampling method works as follows:

1. Generate a random number${\displaystyle u}$ from the standard uniform distribution in the interval${\displaystyle [0,1]}$, i.e. from${\displaystyle U\sim \mathrm{U}\mathrm{n}\mathrm{i}\mathrm{f}[0,1].}$
2. Find thegeneralized inverse of the desired CDF, i.e.${\displaystyle F_X^{-1}(u)}$.
3. Compute${\displaystyle X^{\prime }(u)=F_X^{-1}(u)}$. The computed random variable${\displaystyle X^{\prime }(U)}$ has distribution${\displaystyle F_X}$ and thereby the same law as${\displaystyle X}$.

Expressed differently, given a cumulative distribution function${\displaystyle F_X}$ and a uniform variable${\displaystyle U\in [0,1]}$, the random variable${\displaystyle X=F_X^{-1}(U)}$ has the distribution${\displaystyle F_X}$.^[3]

In the continuous case, a treatment of such inverse functions as objects satisfying differential equations can be given.^[4] Some such differential equations admit explicitpower series solutions, despite their non-linearity.^[5]

• As an example, suppose we have a random variable${\displaystyle U\sim \mathrm{U}\mathrm{n}\mathrm{i}\mathrm{f}(0,1)}$ and acumulative distribution function

${\displaystyle \begin{array}{r}F(x)=1-\exp (-\sqrt{x})\end{array}}$

In order to perform an inversion we want to solve for${\displaystyle F(F^{-1}(u))=u}$

From here we would perform steps one, two and three.

• As another example, we use theexponential distribution with${\displaystyle F_X(x)=1-e^{-\lambda x}}$ for x ≥ 0 (and 0 otherwise). By solving y=F(x) we obtain the inverse function

${\displaystyle x=F^{-1}(y)=-\frac{1}{\lambda }\ln (1-y).}$

It means that if we draw some${\displaystyle y_0}$from a${\displaystyle U\sim \mathrm{U}\mathrm{n}\mathrm{i}\mathrm{f}(0,1)}$ and compute${\displaystyle x_0=F_X^{-1}(y_0)=-\frac{1}{\lambda }\ln (1-y_0),}$ This${\displaystyle x_0}$ has exponential distribution.

The idea is illustrated in the following graph:

Note that the distribution does not change if we start with 1-y instead of y. For computational purposes, it therefore suffices to generate random numbers y in [0, 1] and then simply calculate

${\displaystyle x=F^{-1}(y)=-\frac{1}{\lambda }\ln (y).}$

Let${\displaystyle F}$ be acumulative distribution function, and let${\displaystyle F^{-1}}$ be itsgeneralized inverse function (using theinfimum because CDFs are weakly monotonic andright-continuous):^[6]

Claim: If${\displaystyle U}$ is auniform random variable on${\displaystyle [0,1]}$ then${\displaystyle F^{-1}(U)}$ has${\displaystyle F}$ as its CDF.

Proof:

Inverse transform sampling can be simply extended to cases oftruncated distributions on the interval${\displaystyle (a,b]}$ without the cost of rejection sampling: the same algorithm can be followed, but instead of generating a random number${\displaystyle u}$ uniformly distributed between 0 and 1, generate${\displaystyle u}$ uniformly distributed between${\displaystyle F(a)}$ and${\displaystyle F(b)}$, and then again take${\displaystyle F^{-1}(u)}$.

In order to obtain a large number of samples, one needs to perform the same number of inversions of the distribution. One possible way to reduce the number of inversions while obtaining a large number of samples is the application of the so-called Stochastic Collocation Monte Carlo sampler (SCMC sampler) within apolynomial chaos expansion framework. This allows us to generate any number of Monte Carlo samples with only a few inversions of the original distribution with independent samples of a variable for which the inversions are analytically available, for example the standard normal variable.^[7]

There are software implementations available for applying the inverse sampling method by using numerical approximations of the inverse in the case that it is not available in closed form. For example, an approximation of the inverse can be computed if the user provides some information about the distributions such as the PDF^[8] or the CDF.

• C library UNU.RAN^[9]
• R library Runuran^[10]
• Python subpackage sampling inscipy.stats^[11][12]

• Probability integral transform
• Copula, defined by means of probability integral transform.
• Quantile function, for the explicit construction of inverse CDFs.
• Inverse distribution function for a precise mathematical definition for distributions with discrete components.
• Rejection sampling is another common technique to generate random variates that does not rely on inversion of the CDF.

• Monte Carlo methods
• Non-uniform random numbers

• Articles with short description
• Short description matches Wikidata