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

Inversion Method

• The following property of the generalized inverse can be used as a basis for the generation of pseudo-random numbers that can be regarded as realizations of random variables whose distribution function is an arbitrary monotonically nondecreasing and right-continuous function such that and .
• Recall the following auxiliary result.
• Let be an arbitrary distribution function. Then the function where

 (9)

is called the generalized inverse of the distribution function .
• For arbitrary and

 if and only if (10)

see Lemma WR-4.1.

Theorem 3.4
• Let be a sequence of independent and uniformly distributed random variables on and let be a distribution function.
• Then the random variables where for are independent and their distribution function is given by .

Proof

• The independence of is an immediate consequence of the transformation theorem for independent random variables; see Theorem WR-3.18.
• Furthermore, (10) implies for arbitrary and

Examples

• In the following we discuss some examples illustrating
• how Theorem 3.4 can be used in order to generate pseudo-random numbers
• that can be regarded as realizations of independent random variables with a given distribution function .
• These numbers are also referred to as -distributed pseudo-random numbers ,
• in spite of the fact that the empirical distribution function of the sample
• is only an approximation of for large .
• Note that Theorem 3.4 can only be applied directly if
• the generalized inverse of is given explicitly (i.e. by an analytical formula).
• Unfortunately, this situation is merely an exception.

1. Exponential distribution
• Let and be the distribution function of the Exp-distribution, i.e.

• Then for all .

• By Theorem 3.4,
• we have Exp if and hence also are uniformly distributed on

• and the pseudo-random numbers where

can be regarded as realizations of Exp-distributed random variables
• if are realizations of independent and uniformly on distributed random variables .

2. Erlang distribution
• Let , and let be the distribution function of the Erlang distribution, i.e., of the -distribution where

 (11)

• Then the generalized inverse of 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 if the random variables are independent and Exp-distributed.

• By Theorem 3.4
• the pseudo-random numbers where

can be regarded as realizations of independent -distributed random variables,
• if are realizations of independent and uniformly distributed random variables on .
• In particular, for the pseudo-random numbers can be regarded as realizations of a -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 to be independent and uniformly distributed on .
• By Theorem 3.4, we get that is an Exp-distributed random variable and
• the random vector where

turns out to be N -distributed, i.e., , are independent and N-distributed random variables
• as for arbitrary

where the last but one equality follows from the substitution

whose functional determinant is .
• The pseudo-random numbers where

 (12)

• can thus be regarded as realizations of independent and N-distributed random variables ,
• if are realizations of independent and uniformly on distributed random variables .
• For arbitrary and the pseudo-random numbers where can be regarded as realizations of independent and N -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).

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