Inverse transform sampling

Inverse transform sampling, also known as the inverse probability integral transform or inverse transformation method or Smirnov transform or even golden rule, is a basic method for pseudo-random number sampling, i.e. for generating sample numbers at random from any probability distribution given its cumulative distribution function (cdf). Subject to the restriction that the distribution is continuous, this method is generally applicable (and can be computationally efficient if the cdf can be analytically inverted), but may be too computationally expensive in practice for some probability distributions. The Box–Muller transform is an example of an algorithm that is specific to generating samples from a normal distribution, but is more computationally efficient. It is often the case that, even for simple distributions, the inverse transform sampling method can be improved on: see, for example, the ziggurat algorithm and rejection sampling.

Definition

The probability integral transform states that if X is a continuous random variable with cumulative distribution function F_X, then the random variable Y = F_X(X) has a uniform distribution on [0, 1]. The inverse probability integral transform is just the inverse of this: specifically, if Y has a uniform distribution on [0, 1] and if X has a cumulative distribution F_X, then the cumulative distribution function of the random variable $F_X^{-1}(Y)$ is F_X .

The method

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

• Let X be a random variable whose distribution can be described by the cumulative distribution function F.
• We want to generate values of X which are distributed according to this distribution.

The inverse transform sampling method works as follows:

1. Generate a random number u from the standard uniform distribution in the interval [0,1].
2. Compute the value x such that F(x) = u.
3. Take x to be the random number drawn from the distribution described by F.

Expressed differently, given a continuous uniform variable U in [0, 1] and an invertible cumulative distribution function F, the random variable X = F ⁻¹(U) has distribution F (or, X is distributed F).

A treatment of such inverse functions as objects satisfying differential equations can be given. Some such differential equations admit explicit power series solutions, despite their non-linearity.

Proof of correctness

Let F be a continuous cumulative distribution function, and let F⁻¹ be its inverse function (using the infimum because CDFs are weakly monotonic and right-continuous):

$F^{-1}(u) = \inf\;\{x \mid F(x)\geq u, 0<u<1\}$

Claim: If U is a uniform random variable on (0, 1) then F ^{− 1}(U) follows the distribution F.

Proof:

$\begin{align} & \Pr(F^{-1}(U) \leq x) \\ & {} = \Pr(\inf\;\{y \mid F(y)=U\} \leq x)\quad \text{(by definition of }F^{-1}) \\ & {} = \Pr(U \leq F(x)) \quad \text{(applying }F,\text{ which is monotonic, to both sides)} \\ & {} = F(x)\quad \text{(because }\Pr(U \leq y) = y,\text{ since }U\text{ is uniform on the unit interval)} \end{align}$

See also

• 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.