next up previous contents
Next: Quotients of Uniformly Distributed Up: Transformation of Uniformly Distributed Previous: Transformation Algorithms for Discrete   Contents


Acceptance-Rejection Method

Theorem 3.5    


Proof
 

Remarks
 


In the general (i.e. not necessarily discrete) case one can proceed in a similar way. The following result will serve as foundation for constructing acceptance-rejection algorithms.


Theorem 3.6    

Proof
 


In the same way we obtain the following vectorial version of Theorem 3.6.

Theorem 3.7    

Examples
 
  1. Uniform distribution on bounded Borel sets 
    • Let the random vector $ {\mathbf{X}}:\Omega\to\mathbb{R}^m$ (with distribution function $ F$) be uniformly distributed on the square $ (-1,1]^m$ and let $ B\in\mathcal{B}((-1,1]^m$ be an arbitrary Borel subset of $ (-1,1]^m$ of positive Lebesgue measure $ \vert B\vert$.
    • Then the distribution function $ G:\mathbb{R}^m\to[0,1]$ given by

      $\displaystyle G({\mathbf{y}})=\int_{(-\infty,{\mathbf{y}}]}\;\frac{{1\hspace{-1...
...}{\vert B\vert}\;dF({\mathbf{x}})\,,\qquad\forall\,{\mathbf{y}}\in\mathbb{R}^m
$

      is absolutely continuous with respect to $ F$ and we obtain for the (Radon-Nikodym) density
      $ g:\mathbb{R}^m\to[0,\infty)$ that

      $\displaystyle g({\mathbf{x}})=\frac{{1\hspace{-1mm}{\rm I}}({\mathbf{x}}\in B)}{\vert B\vert}\le
c=\vert B\vert^{-1}$   and$\displaystyle \qquad \frac{g({\mathbf{x}})}{c}\;={1\hspace{-1mm}{\rm I}}({\mathbf{x}}\in
B)\,, \qquad\forall\,{\mathbf{x}}\in\mathbb{R}^m\,.
$

    • By Theorem 3.7 we can now in the following way generate pseudo-random vectors $ {\mathbf{y}}_1,{\mathbf{y}}_2,\ldots$ that are uniformly distributed on $ B$.
      1.
      Generate $ m$ pseudo-random numbers $ u_1,\ldots,u_m$ that are uniformly distributed on the interval $ (0,1]$.
      2.
      If $ (2u_1-1,\ldots,2u_m-1)^\top\not\in B$, then return to step 1.
      3.
      Otherwise put $ {\mathbf{y}}=(2u_1-1,\ldots,2u_m-1)^\top$.


  2. Normal distribution 
    • As an alternative to the Box-Muller algorithm discussed in Section 3.2.1 we will now introduce another method to generate normally distributed pseudo-random numbers,
      • which is often called the polar method.
      • Notice that the polar method avoids calculating the trigonometric functions in (12).
    • Let the random vector $ (V_1,V_2)$ be uniformly distributed on the unit circle $ B$, where
      $ B=\{(x_1,x_2)\in\mathbb{R}^2:\,x_1^2+x_2^2\le 1\}$.
    • Then, the random vector $ (Y_1,Y_2)$ where

      $\displaystyle Y_1=\sqrt{-2 \log(V_1^2+V_2^2)}\;
\frac{V_1}{\sqrt{V_1^2+V_2^2}}\,,\qquad Y_2=\sqrt{-2
\log(V_1^2+V_2^2)}\; \frac{V_2}{\sqrt{V_1^2+V_2^2}}
$

      is N $ ({\mathbf{o}},{\mathbf{I}})$-distributed, i.e., $ Y_1$, $ Y_2$ are independent and N$ (0,1)$-distributed random variables. This can be seen as follows.
      • By the substitution

        $\displaystyle v_1=r\cos \theta\,,\qquad v_2=r\sin \theta\,,
$

      • i.e. by a transformation into polar coordinates we obtain for arbitrary $ y_1,y_2\in\mathbb{R}$
        $\displaystyle {P(Y_1\le y_1,\, Y_2\le y_2)}$
          $\displaystyle =$ $\displaystyle \frac{1}{\pi}\;\int_B {1\hspace{-1mm}{\rm I}}\Bigl(\frac{v_1\sqrt...
...v_2
\sqrt{-2 \log(v_1^2+v_2^2)}}{\sqrt{v_1^2+v_2^2}}\,\le
y_2\Bigr)\,d(v_1,v_2)$  
          $\displaystyle =$ $\displaystyle \frac{1}{\pi}\;\int_0^{2\pi}\int_0^1 r\,{1\hspace{-1mm}{\rm I}}\B...
...\theta\,\le y_1\,,\,
\sqrt{-2 \log(r^2)}\; \sin\theta\le y_2\Bigr)\,dr\,d\theta$  
          $\displaystyle =$ $\displaystyle \frac{1}{2}\;\frac{1}{2\pi}\;\int_0^{2\pi}\int_0^\infty
{1\hspace...
...}\cos\theta\le y_1,\, \sqrt{x}\sin\theta\le
y_2\Bigr)\;e^{-x/2}\,dx\,d\theta\,,$  

      • where the last equality results from the following substitution:

        $\displaystyle x=-2 \log(r^2)$   bzw.$\displaystyle \qquad -\;\frac{1}{2}\;
e^{-x/2}\,dx=2r\,dr\,.
$

      • By the same argument that was used to verify formula (12) in Section 3.2.1 one can check that the last term can be written as the product $ F(y_1)F(y_2)$ of two N$ (0,1)$-distribution functions.
    • The pseudo-random numbers $ y_1,\ldots,y_{2n}$ with

      $\displaystyle y_{2k-1}=\sqrt{-2 \log(v_{2k-1}^2+v_{2k}^2)}\;
\frac{v_{2k-1}}{\s...
...sqrt{-2 \log(v_{2k-1}^2+v_{2k}^2)}\;
\frac{v_{2k}}{\sqrt{v_{2k-1}^2+v_{2k}^2}}
$

      • can thus be regarded as realizations of independent and N$ (0,1)$-distributed random variables,
      • if $ (v_1,v_2),\ldots,(v_{2n-1},v_{2n})$ are realizations of the random variables $ (V_1,V_2),\ldots,(V_{2n-1},V_{2n})$ that are independent and uniformly distributed on the unit circle

        $\displaystyle B=\{(x_1,x_2)\in\mathbb{R}^2:\,x_1^2+x_2^2\le 1\}\,.$

      • Those can be generated via acceptance-rejection sampling as explained in the last example.



next up previous contents
Next: Quotients of Uniformly Distributed Up: Transformation of Uniformly Distributed Previous: Transformation Algorithms for Discrete   Contents
Ursa Pantle 2006-07-20