Inversion Method

1. Inversion Method

The inversion method allows to sample from a distribution \(\pi\) using draws from a uniform distribution \(\mathcal{U}_{[0, 1]}\), and the quantile function associated with \(\pi\). Consider a real-valued r.v. \(X\) and its associated CDF \(F(x)=\mathbb{P}(X \leq x)\).

The CDF \(F: \mathbb{R} \to [0, 1]\) is

• increasing, i.e. if \(x \leq y\), then \(F(x) \leq F(y)\);

• right continuous, i.e. \(F(x+\varepsilon) \to F(x)\) as \(\varepsilon \to 0\);

• \(F(x) \to 0\) as \(x \to -\infty\) and \(F(x) \to 1\) as \(x \to +\infty\).

Define the generalized inverse \[F^-(u)=\inf_{x \in \mathbb{R}} \{F(x) \geq u\},\] a.k.a. the quantile function or inverse CDF. Note that \(F^-(u)=F^{-1}(u)\) if \(F\) is continuous.

Theorem 1.1 (Inversion Method)    Let \(F\) be a CDF and \(U \sim \mathcal{U}_{[0, 1]}\), then \(X=F^-(U)\) has CDF \(F\).

Proof. If \(F^-(u) \leq x\), then \(u \leq F(x).\) Thus for \(U \sim \mathcal{U}_{[0, 1]}\), we have \[\mathbb{P}(X=F^-(U) \leq x)=\mathbb{P}(U \leq F(x))=F(x),\] i.e., \(F\) is the CDF of \(F^-(U)\).

\(\square\)

If \(U \sim \mathcal{U}_{[0, 1]}\) and \(F^-\) is the quantile function associated with a distribution \(\pi\), then \(F^-(U)\) is distributed according to \(\pi\).

2. Example

Example 2.1 (Exponential Distribution)    If \(F(x)=1-e^{-\lambda x}\) for all \(x \in \mathbb{R}^+\), then \[F^-(u)=F^{-1}(u)=-\frac{\ln(1-u)}{\lambda}.\] Hence \(\displaystyle -\frac{\ln(1-U)}{\lambda}\) and \(\displaystyle -\frac{\ln(U)}{\lambda}\) where \(U \sim \mathcal{U}_{[0, 1]}\) are distributed according to an exponential distribution \(\mathcal{E}(\lambda)\).

Example 2.2 (Cauchy Distribution)    The Cauchy distribution has CDF \[F(x)=\frac{1}{2}+\frac{\arctan(x)}{\pi}\] for all \(x \in \mathbb{R}\). Hence we have \[F^-(u)=F^{-1}(u)=\tan\left(\pi\left(u-\frac{1}{2}\right)\right).\]

Example 2.3 (Geometric Distribution)    \(F(x)=1-q^x\) for \(x=1, 2, \ldots\), where \(0<p<1\) and \(q=1-p\). The smallest \(x \in \mathbb{N}\) giving \(F(x) \geq u\) is the smallest \(x \in \mathbb{N}\) satisfying \(\displaystyle x \geq \frac{\ln(1-u)}{\ln(q)}\). Hence \[x=F^-(u)=\left\lceil \frac{\ln(1-u)}{\ln(q)} \right\rceil\] where we can replace \(1-u\) with \(u\).

3. Comment

The inversion method can be used to generate r.v.s. with values in any countable set and requires point-wise evaluation of the quantile function. The limitation is that we need to be able to evaluate the generalized inverse of the CDF \(F^-\), which is typically unknown for the distribution encountered in real application.