Inversion

Theorem (Inversion)

Let $U\sim U[0,1]$ be on the Uniform Distribution and let $F$ be the target CDF. Let $C=F^{-1}(U)$ where $X$ is a s? RV. Then $X\sim F$.

Consider the following CDF of $F$.

What exactly is $F^{-1}$? First, $F$ is an increasing function to $1$ (or asymptotically to $1$). If we take some point $u_1$ with the corresponding domain $F^{-1}(u_1)$, then apart from the flat portion, it is clear what the value should be.

Now for the range of $F$ where the value is neither increasing nor decreasing (the red portion in the graph), then we define

$$F^{-1}=\inf \{z\in \mathbb{R}|F(z)\}$$

or the Infimum. In particular,

$$\begin{array}{rl}P(X\le x)& =P(F^{-1}(U)\le x)\\ & =P(U\le F(X))\\ & =F_U(F(X))\\ & =F(X)\end{array}$$

which is sort of a “baby sampling algorithm”.

Inversion Algorithm

This gives us the following algorithm,

1. Input: CDF $F$ (target)
2. Output Sample $X\sim F$
3. Step 1: Generate $U\sim U[0,1]$
4. Step 2: Assign $X\leftarrow F^{-1}(U)$

Example 1

Suppose we sampled the following RV with the PDF

$$f(x)=\{\begin{array}{ll}0& x<0\\ \lambda e^{-\lambda x}& x\ge 0\end{array}$$

or the Exponential distribution with parameter $\lambda$.

Solution: We know that the CDF is

$${\int }_{-\infty }^x\lambda e^{-\lambda s}ds=\{\begin{array}{ll}0& x<0\\ 1-e^{-\lambda x}& x\ge 0\end{array}$$

Then we finish by

$$\begin{array}{rl}F(X)& =U\\ 1-e^{-\lambda X}=U& \\ X=-\frac{1}{\lambda }\ln (1-U)& \end{array}$$

So, if $U\sim U[0,1]$, then

$$X=-\frac{1}{\lambda }\ln (1-U)\sim f$$

---

More generally, we want to know more about the Transformation of Random Variables.

Discrete Case

We can apply the same methods used of continuous RVs on discrete RVs.

Let RV $X\in \{x_1,x_2,\dots \}$ with PMF $P(X=x_i)=p_i$ and CDF $F(n)$ defined below. Also $x_i$ is strictly increasing.

1. Sample $U\sim U[0,1]$.
2. Let $F^{-1}(u)=\min \{z|F(z)\ge u\}=x_h$ for $h=\min \{s|{\sum }_{i=1}^s{p}_i\ge u\}$. Basically let the inverse be the minimum $x$ value that has the minimum probability of occurring.
3. Set $X\leftarrow x_h$.