Inverse transform sampling

The inverse transform sampling method is a method of sampling a number at random from any probability distribution given its cumulative distribution function (cdf).

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 cdf F.
• We want to generate values of X which are distributed according to this distribution.

Many programming languages have the ability to generate pseudo-random numbers which are effectively distributed according to the standard uniform distribution. If a random variable has that distribution, then the probability of its falling within any subinterval (a, b) of the interval from 0 to 1 is just the length b − a of that subinterval.

The inverse transform sampling method works as follows:

1. Generate a random number from the standard uniform distribution; call this u.
2. Compute the value x such that ${\displaystyle F(x)=u}$ ; call this x_chosen.
3. Take x_chosen to be the random number drawn from the distribution described by F.

Proof of correctness

Let F be a continuous cumulative distribution function, and let ${\displaystyle F^{-1}}$  be its inverse function:^[1]

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

Claim: If U is a uniform random variable on ${\displaystyle (0;1)}$  then ${\displaystyle F^{-1}(U)}$  follows the distribution F.

Proof:

${\displaystyle \Pr(F^{-1}(U)\leq x)\!}$ 

${\displaystyle =\Pr(\inf \;\{x\mid F(x)=U\}\leq x)\!}$     (by the definition of ${\displaystyle F^{-1}}$ )

${\displaystyle =\Pr(U\leq F(x))\!}$     (applying F, which is monotonic, to both sides)

${\displaystyle =F(x)\!}$     (because ${\displaystyle \Pr(U\leq y)=y}$ , since U is uniform on the unit interval)

References

1. Luc Devroye. Non-Uniform Random Variate Generation. New York: Springer-Verlag, 1986. (online) See chapter 2, section 2, p. 28.