Inverse transform sampling

For any random variable ${\displaystyle X\in \mathbb {R} }$, the random variable ${\displaystyle F_{X}^{-1}(U)}$ has the same law as ${\displaystyle X}$, where ${\displaystyle F_{X}^{-1}}$ is the generalized inverse of the cumulative distribution function ${\displaystyle F_{X}}$ of ${\displaystyle X}$ and ${\displaystyle U}$ is uniform on ${\displaystyle [0,1]}$.[4]

For continuous random variables, the inverse probability integral transform is indeed the inverse of the probability integral transform, which states that for a continuous random variable ${\displaystyle X}$ with cumulative distribution function ${\displaystyle F_{X}}$, the random variable ${\displaystyle U=F_{X}(X)}$ is uniform on ${\displaystyle [0,1]}$.

Graph of the inversion technique from ${\displaystyle x}$ to ${\displaystyle F(x)}$. On the bottom right we see the regular function and in the top left its inversion.

From ${\displaystyle U\sim \mathrm {Unif} [0,1]}$, we want to generate ${\displaystyle X}$ with CDF ${\displaystyle F_{X}(x).}$ We assume ${\displaystyle F_{X}(x)}$ to be a continuous, strictly increasing 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){\overset {d}{=}}X}$. We will have

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

where the last step used that ${\displaystyle \Pr(U\leq 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).}$

Schematic of the inverse transform sampling. The inverse function of ${\displaystyle y=F_{X}(x)}$ can be defined by ${\displaystyle F_{X}^{-1}(y)=\mathrm {inf} \{x|F_{X}(x)\geq y\}}$.

An animation of how inverse transform sampling generates normally distributed random values from uniformly distributed random values

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

• Let ${\displaystyle X}$ be a random variable whose distribution can be described by the cumulative 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 {Unif} [0,1].}$
2. Find the generalized inverse of the desired CDF, i.e. ${\displaystyle F_{X}^{-1}(u)}$.
3. Compute ${\displaystyle X'(u)=F_{X}^{-1}(u)}$. The computed random variable ${\displaystyle X'(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}}$.[4]

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

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

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

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

${\displaystyle {\begin{aligned}F(F^{-1}(u))&=u\\1-\exp \left(-{\sqrt {F^{-1}(u)}}\right)&=u\\F^{-1}(u)&=(-\log(1-u))^{2}\\&=(\log(1-u))^{2}\end{aligned}}}$

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

• As another example, we use the exponential 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 {Unif} (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:

Random numbers y_i are generated from a uniform distribution between 0 and 1, i.e. Y ~ U(0, 1). They are sketched as colored points on the y-axis. Each of the points is mapped according to x=F⁻¹(y), which is shown with gray arrows for two example points. In this example, we have used an exponential distribution. Hence, for x ≥ 0, the probability density is ${\displaystyle \varrho _{X}(x)=\lambda e^{-\lambda \,x}}$ and the cumulative distribution function is ${\displaystyle F(x)=1-e^{-\lambda \,x}}$. Therefore, ${\displaystyle x=F^{-1}(y)=-{\frac {\ln(1-y)}{\lambda }}}$. We can see that using this method, many points end up close to 0 and only few points end up having high x-values - just as it is expected for an exponential distribution.

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 a cumulative distribution function, and let ${\displaystyle F^{-1}}$ be its generalized inverse function (using the infimum because CDFs are weakly monotonic and right-continuous):[7]

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

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

Proof:

${\displaystyle {\begin{aligned}&\Pr(F^{-1}(U)\leq x)\\&{}=\Pr(U\leq F(x))\quad &(F{\text{ is right-continuous, so }}\{u:F^{-1}(u)\leq x\}=\{u:u\leq F(x)\})\\&{}=F(x)\quad &({\text{because }}\Pr(U\leq u)=u,{\text{ when }}U{\text{ is uniform on }}[0,1])\\\end{aligned}}}$

Inverse transform sampling can be simply extended to cases of truncated 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 a polynomial 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.[8]

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