Acceptance-Rejection Method

- In this section we discuss another method for the generation of
pseudo-random numbers
- that can be regarded as realizations of independent and identically distributed random variables . Their distribution function is assumed to be given; it is denoted by .
- This method also requires a sequence of independent and identically distributed pseudo-random numbers , but we abandon the condition that they need to be uniformly distributed on .
- The only condition we impose on their distribution function is
that needs to be
*absolutely continuous*with respect to with bounded density , - i.e., for some constant , we have

- First of all we consider the discrete case.
- Let for all , and let and be two arbitrary probability functions such that for all implies .
- Let be a random variable for all ,
- and let be a positive number

- Let be a sequence of independent and identically distributed random vectors whose components are independent. Furthermore, let be a -uniformly distributed random variable and be distributed according to .
- Then
- the random variable

is geometrically distributed with expectation , i.e., , - and the random variable is distributed according to .

- the random variable

**Proof**-
- By the definition of given in (21), we obtain
for all

- where and

- This shows .

- where and
- Furthermore, for any such that , we get that

and for all such that

- By the definition of given in (21), we obtain
for all
**Remarks**-
- Theorem 3.5 implies that the mean number of -distributed pseudo-random numbers necessary to obtain a -distributed random number is .
- In case there are several alternatives for the choice of the the
distribution function ,
- possessing equally nice properties with respect to the generation of -distributed pseudo-random numbers,
- then one should choose the distribution function with the smallest .

- Furthermore, as a consequence of Theorem 3.5,

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.

- Let be two arbitrary distribution functions such that holds.
- Let be a sequence of independent and identically distributed random vectors whose components are independent. Furthermore, let be a -uniformly distributed random variable and be distributed according to .
- Then the random variable

is geometrically distributed with expectation , i.e., and the random variable is distributed according to .

**Proof**-
- Similarly to the proof of Theorem 3.5 we obtain
for any where

- Furthermore, for all
we have

where .

- Similarly to the proof of Theorem 3.5 we obtain
for any where

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

- Let be an arbitrary but fixed natural number and let
be two arbitrary distribution functions
(of -dimensional
random vectors) and let be a constant such that

- Let be a sequence of independent and identically distributed random vectors whose components are also independent. Furthermore, let be a -uniformly distributed random variable and be distributed according to .
- Then the random variable

is geometrically distributed with expectation , i.e., and the random vector is distributed according to .

**Examples**-
*Uniform distribution on bounded Borel sets*- Let the random vector (with distribution function ) be uniformly distributed on the square and let be an arbitrary Borel subset of of positive Lebesgue measure .
- Then the distribution function
given by

thatand - By Theorem 3.7 we can now in the following way
generate pseudo-random vectors
that are
uniformly distributed on .
- 1.
- Generate pseudo-random numbers that are uniformly distributed on the interval .
- 2.
- If , then return to step 1.
- 3.
- Otherwise put .

*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).

- which is often called the
- Let the random vector be uniformly distributed on the
unit circle , where

. - Then, the random vector where
- By the substitution
- i.e. by a transformation into polar coordinates we obtain for
arbitrary

- where the last equality results from the following substitution:
bzw.
- 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 of two N-distribution functions.

- By the substitution
- The pseudo-random numbers
with
- can thus be regarded as realizations of independent and N-distributed random variables,
- if
are realizations of the
random variables
that are
independent and uniformly distributed on the unit circle
- Those can be generated via acceptance-rejection sampling as explained in the last example.

- 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,