Next: Acceptance-Rejection Method Up: Transformation of Uniformly Distributed Previous: Inversion Method   Contents

### Transformation Algorithms for Discrete Distributions

• If pseudo-random numbers need to be generated
• that can be regarded as realizations of discrete random variables
• taking the values with probabilities for ,
• then it is sometimes advisable to proceed as follows:
• Let be a -uniformly distributed random variable and let the random variable be given by

 (13)

• Then for all .
• The pseudo-random numbers where

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

Example
(geometric distribution)
• We consider the following values for and the corresponding probabilities .
• Let for , and for , let

• Then, for all ,

 (14)

and .

• Furthermore, we consider the random variable

 (15)

where is a -uniformly distributed random variable and denotes the integer part of .

• Then for all , i.e. Geo,
• as (14) and (15) imply

• where the random variable is also uniformly distributed on .

• The pseudo-random numbers where

• can thus be regarded as realizations of independent and geometrically distributed random variables Geo
• if are realizations of independent random variables that are uniformly distributed on the interval .

For some discrete distributions there are specific transformation algorithms allowing the generation of pseudo-random numbers having this distribution.

Examples

1. Poisson distribution (with small expectation )
• If is a small number, then the following procedure is appropriate to generate Poisson-distributed pseudo-random numbers
• by transformation of exponentially distributed pseudo-random numbers (as in Section 3.2.1)
• or directly based on -uniformly distributed pseudo-random numbers.
• Let the random variables be independent and Exp-distributed.
• If we consider the random variable , formula (11) for the distribution function of the Erlang-distribution yields for all

• In other words we obtained Poi.
• The pseudo-random numbers where

 (16)

and

 (17)

where and for ,
• can thus be regarded as realizations of independent and Poi-distributed random variables,
• if are realizations of Exp-distributed random variables and
• if are realizations of independent random variables that are uniformly distributed on the interval , respectively.
• Remarks
• As the expectation of the Poi-distribution is given by , the mean number of uniformly distributed pseudo-random numbers necessary in order to generate a new Poi-distributed pseudo-random number is also .
• For large this effort can be reduced if one proceeds as follows.

2. Poisson distribution (with large expectation )
• If is large, and for ,
• then the procedure based directly on the transformation formula (13) is more appropriate to generate Poi-distributed pseudo-random numbers,
• The validity of the inequalities

 (18)

needs to be checked in the order defined below.
• Note that the recursion formula

is applied to calculate the sums for .
• Let be the integer part of . Then it is firstly checked if .
• If this inequality holds it is checked if where we define .
• If the inequality does not hold then it is checked if and we also define .
• For the expectation of the necessary number of checking steps we obtain the approximation

• where the last approximation uses the fact that the random variable is approximately N-distributed for large for the following reasons.
• As the Poisson distribution is stabile under convolutions, i.e.,

the random variable Poi can be viewed as the sum of independent and Poi -distributed random variables . The last approximation then follows from the central limit theorem for sums of independent and identically distributed random variables; see Theorem WR-5.16.
• We observe that
• for increasing the mean number of checking steps only grows with rate if this simulation procedure is applied,
• whereas for the formerly discussed method generating Poi-distributed pseudo-random numbers the necessary number of standard pseudo-random numbers grows linearly in .

3. Binomial distribution
• For the generation of binomially distributed pseudo-random numbers one can proceed similarly to the Poisson case.
• For arbitrary but fixed numbers and where let

and

• For the sums are calculated via the recursion formula

• If is small, then
• the validity of the inequalities (18) is checked in the natural order
• starting at and defining .
• If is large,
• then it is more efficient to check the validity of the inequalities (18) in the following order. It is firstly checked if .
• If this inequality holds it is checked if where we also define .
• If the inequality does not hold it is checked if where we again define .

Next: Acceptance-Rejection Method Up: Transformation of Uniformly Distributed Previous: Inversion Method   Contents
Ursa Pantle 2006-07-20