Next: Quotients of Uniformly Distributed Up: Transformation of Uniformly Distributed Previous: Transformation Algorithms for Discrete   Contents

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

 and (19)

• 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

 (20)

Theorem 3.5
• 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

 (21)

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

Proof

• By the definition of given in (21), we obtain for all

• where and

• This shows .
• Furthermore, for any such that , we get that

and for all such that

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,
• the values and of the density in (19) and (20), respectively need only be known up to a constant factor.

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

 (22)

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 .

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

Theorem 3.7
• 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

 and (23)

• 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

 (24)

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

Examples

1. 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

is absolutely continuous with respect to and we obtain for the (Radon-Nikodym) density
that

and

• 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.
3.
Otherwise put .

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 be uniformly distributed on the unit circle , where
.
• Then, the random vector where

is N -distributed, i.e., , are independent and N-distributed random variables. This can be seen as follows.
• 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.
• 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.

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