Inversion Method

• The following property of the generalized inverse can be used as a basis for the generation of pseudo-random numbers $x_1,x_2\ldots$ that can be regarded as realizations of random variables $X_1,X_2\ldots$ whose distribution function $F:\mathbb{R}\to[0,1]$ is an arbitrary monotonically nondecreasing and right-continuous function such that $\lim_{x\to-\infty} F(x)=0$ and $\lim_{x\to\infty} F(x)=1$.
• Recall the following auxiliary result.
  • Let $F:\mathbb{R}\to[0,1]$ be an arbitrary distribution function. Then the function $F^{-1}:(0,1]\to\mathbb{R}\cup\{\infty\}$ where

    $$F^{-1}(y)=\inf\{x:\, F(x)\ge y\}$$ (9)

    
    
    is called the generalized inverse of the distribution function $F$.
  • For arbitrary $x\in\mathbb{R}$ and $y\in(0,1)$

    $$y\le F(x) \qquad F^{-1}(y)\le x\,,$$ (10)

    
    
    see Lemma WR-4.1.

Theorem 3.4    

• Let $U_1,U_2,\ldots$ be a sequence of independent and uniformly distributed random variables on $(0,1]$ and let $F:\mathbb{R}\to[0,1]$ be a distribution function.
• Then the random variables $X_1,X_2,\ldots$ where $X_i=F^{-1}(U_i)$ for $i=1,2,\ldots$ are independent and their distribution function is given by $F$.

Proof

 

• The independence of $X_1,X_2,\ldots$ is an immediate consequence of the transformation theorem for independent random variables; see Theorem WR-3.18.
• Furthermore, (10) implies for arbitrary $x\in\mathbb{R}$ and $i\in\mathbb{N}$
  $$P(X_i\le x)=P\bigl(F^{-1}(U_i)\le x\bigr) \stackrel{(\ref{equ.gen.dan})}{=} P\bigl(U_i\le F(x)\bigr)=F(x)\,.$$
  
   
    $\Box$
  
  
  

Examples

 

• In the following we discuss some examples illustrating
  • how Theorem 3.4 can be used in order to generate pseudo-random numbers $x_1,x_2\ldots$
  • that can be regarded as realizations of independent random variables $X_1,X_2\ldots$ with a given distribution function $F:\mathbb{R}\to[0,1]$.
• These numbers are also referred to as $F$-distributed pseudo-random numbers $x_1,x_2\ldots$,
  • in spite of the fact that the empirical distribution function $\widehat F_n$ of the sample $x_1,\ldots,x_n$
  • is only an approximation of $F$ for large $n$.
• Note that Theorem 3.4 can only be applied directly if
  • the generalized inverse $F^{-1}$ of $F$ is given explicitly (i.e. by an analytical formula).
  • Unfortunately, this situation is merely an exception.

1. Exponential distribution
   • Let $\lambda>0$ and $F:\mathbb{R}\to[0,1]$ be the distribution function of the Exp$(\lambda)$-distribution, i.e.
     $$F(x)=\left\{\begin{array}{ll} 1-e^{-\lambda x} &\mbox{if $x\ge 0$,}\\ 0 &\mbox{if $x<0$.} \end{array}\right.$$

   • Then $F^{-1}(u)=-\lambda^{-1}\log (1-u)$ for all $u\in(0,1]$.

     
     

   • By Theorem 3.4,
     • we have $X=-\lambda^{-1}\log U\sim$ Exp$(\lambda)$ if $U$ and hence also $1-U$ are uniformly distributed on $(0,1]$

     • and the pseudo-random numbers $x_1,\ldots,x_n$ where
       $$x_i=-\;\frac{\log u_i}{\lambda}$$   $$\mbox{for $i=1,\ldots,n$}$$$$$$
       can be regarded as realizations of Exp$(\lambda)$-distributed random variables
     • if $u_1,\ldots,u_n$ are realizations of independent and uniformly on $(0,1]$ distributed random variables $U_1,\ldots,U_n$.

   
   

2. Erlang distribution
   • Let $\lambda>0$, $r\in\mathbb{N}$ and let $F:\mathbb{R}\to[0,1]$ be the distribution function of the Erlang distribution, i.e., of the $\Gamma(\lambda,r)$-distribution where

     $$F(x)=\left\{\begin{array}{ll} \displaystyle \int_0^x\displaystyle... ...-1}}{(r-1)!}\;dv &\mbox{if $x\ge 0$,}\\ 0 &\mbox{if $x<0$.} \end{array}\right.$$ (11)

     
     

     
     

   • Then the generalized inverse $F^{-1}$ of $F$ cannot be determined explicitly and therefore Theorem 3.4 cannot be applied directly.

     
     

   • However, in Section 1.3.1 of the course ,,Statistik I'' we showed that $X_1+\ldots+X_r\sim\Gamma(\lambda,r)$ if the random variables $X_1,\ldots,X_r$ are independent and Exp$(\lambda)$-distributed.

     
     

   • By Theorem 3.4
     • the pseudo-random numbers $y_1,\ldots,y_n$ where
       $$y_i=x_{r(i-1)+1}+\ldots+ x_{ri}=-\;\frac{\log \bigl(u_{r(i-1)+1}\cdot\ldots\cdot u_{ri}\bigr)}{\lambda}\qquad \mbox{for $i=1,\ldots,n$}$$
       can be regarded as realizations of independent $\Gamma(\lambda,r)$-distributed random variables,
     • if $u_1,\ldots,u_{rn}$ are realizations of independent and uniformly distributed random variables on $(0,1]$.
     • In particular, for $\lambda=1/2$ the pseudo-random numbers $y_1,\ldots,y_n$ can be regarded as realizations of a $\chi^2_{2r}$-distributed random variable.

   
   

3. Normal distribution
   • In order to generate normally distributed pseudo-random numbers one can apply the so-called Box-Muller algorithm, which also requires exponentially distributed pseudo-random numbers.
   • Assume the random numbers $U_1,U_2$ to be independent and uniformly distributed on $(0,1]$.
     • By Theorem 3.4, we get that $X=-2\log U_1$ is an Exp$(1/2)$-distributed random variable and
     • the random vector $(Y_1,Y_2)$ where
       $$Y_1=\sqrt{X}\cos(2\pi U_2)\,,\qquad Y_2=\sqrt{X}\sin(2\pi U_2)$$
       turns out to be N $({\mathbf{o}},{\mathbf{I}})$-distributed, i.e., $Y_1$, $Y_2$ are independent and N$(0,1)$-distributed random variables
     • as for arbitrary $y_1,y_2\in\mathbb{R}$
       

       $$P(Y_1\le y_1,\, Y_2\le y_2) = P\Bigl(\sqrt{-2\log U_1}\cos(2\pi U_2)\le y_1,\, \sqrt{-2\log U_1}\sin(2\pi U_2)\le y_2\Bigr)$$

       $$= \frac{1}{2}\;\int_0^1\int_0^\infty {1\hspace{-1mm}{\rm I}}\Bigl(\sqrt{x}\cos(2\pi u)\le y_1,\, \sqrt{x}\sin(2\pi u)\le y_2\Bigr)e^{-x/2}\,dx\,du$$

       $$= \frac{1}{2\pi}\;\int_{-\infty}^{y_2}\int_{-\infty}^{y_1} e^{-(v^2+w^2)/2}\,dv\,dw$$

       $$= \frac{1}{\sqrt{2\pi}}\;\int_{-\infty}^{y_1} e^{-v^2/2}\,dv\; \frac{1}{\sqrt{2\pi}}\;\int_{-\infty}^{y_2} e^{-w^2/2}\,dw\,,$$

       
       
       where the last but one equality follows from the substitution
       $$v=\sqrt{x}\cos(2\pi u)\,,\qquad w=\sqrt{x}\sin(2\pi u)$$
       whose functional determinant is $\pi$.
   • The pseudo-random numbers $y_1,\ldots,y_{2n}$ where

     $$y_{2k-1}=\sqrt{-2\log u_{2k-1}}\cos(2\pi u_{2k})\,,\qquad y_{2k}=\sqrt{-2\log u_{2k-1}}\sin(2\pi u_{2k})$$ (12)

     
     
     • can thus be regarded as realizations of independent and N$(0,1)$-distributed random variables ,
     • if $u_1,\ldots,u_{2n}$ are realizations of independent and uniformly on $(0,1]$ distributed random variables $U_1,\ldots,U_{2n}$.
   • For arbitrary $\mu\in\mathbb{R}$ and $\sigma^2>0$ the pseudo-random numbers $y^\prime_1,\ldots,y^\prime_{2n}$ where $y_i^\prime=\sigma(y_i+\mu)$ can be regarded as realizations of independent and N $(\mu,\sigma^2)$-distributed random variables.

     
     

   • Remarks 
     • A faster algorithm for the generation of normally distributed pseudo-random numbers is obtained if additionally a method of rejection sampling is applied that will be introduced in Section 3.2.3.
     • This method avoids the relatively time-consuming computation of the trigonometric functions in (12).