5.2 The iverse probability method for generating random variables

The iverse probability method for generating random variables

Once the generation of the uniform random variable is established, it can be used to generate other types of random variables.

The continuous case

THEOREM I

Let X have a continuous distribution $F_X\left(x\right)$ , so that $F_X^{-1}\left(\alpha \right)$ exists for $0<\alpha <1$ (and is hopefully countable). Then the random variable $F_X^{-1}\left(U\right)$ has distribution $F_X\left(x\right)$ , U is uniformly distributed on (0,1).

PROOF

Because $F_X\left(x\right)$ is monotone. Thus,

The last step follows because U is uniformly distributed on (0,1). Diagrammatically, we have that $\left(X\le x\right)$ if and only if $\left[U\le F_X\left(x\right)\right]$ , an event of probability $F_X\left(x\right)$ .

As long as we can invert the distribution function $F_X\left(x\right)$ to get the inverse distribution function $F_X^{-1}\left(\alpha \right)$ , the theorem assures us we can start with a pseudo-random uniform variable U and turn into a random variable $F_X^{-1}\left(U\right)$ , which has the required distribution $F_X\left(x\right)$ .

The discrete case

Let X have a discrete distribution $F_X\left(x\right)$ that is, $F_X\left(x\right)$ jumps at points $x_k=\mathrm{0,1,2,...}$ . Usually we have the case that $x_k=k$ , so that X is an integer value.

Let the probability function be denoted by

The probability distribution function is then,

and the reliability or survivor function is

The survivor function is sometimes easier to work with than the distribution function, and in fields such as reliability, it is habitually used. The inverse probability integral transform method of generating discrete random variables is based on the following theorem.

THEOREM

Let U be uniformly distributed in the interval (0,1). Set $X=x_k$ whenever $F_X\left(x_{k-1}\right)<U\le F_X\left(x_k\right)$ , for $k=\mathrm{0,1,2,...}$ with $F_X\left(x_{-1}\right)=0$ . Then X has probability function $p_k$ .

PROOF

By definition of the procedure,

$X=x_k$ if and only if $F_X\left(x_{k-1}\right)<U\le F_X\left(x_k\right)$ .

Therefore,

By the definition of the distribution function of a uniform (0,1) random variable.

Thus the inverse probability integral transform algorithm for generating X is to find $x_k$ such that $U\le F_X\left(x_k\right)$ and $U>F_X\left(x_{k-1}\right)$ and then set $X=x_k$ .

In the discrete case, there is never any problem of numerically computing the inverse distribution function, but the search to find the values $F_X=\left(x_k\right)$ and $F_X\left(x_{k-1}\right)$ between which U lies can be time-consuming, generally, sophisticated search procedures are required. In implementing this procedure, we try to minimize the number of times one compares U to $F_X=\left(x_k\right)$ . If we want to generate many of X , and $F_X=\left(x_k\right)$ is not easily computable, we may also want to store $F_X=\left(x_k\right)$ for all k rather than recomputed it. Then we have to worry about minimizing the total memory to store values of $F_X=\left(x_k\right)$ .