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

- Then for all .

- Let be a -uniformly distributed random variable and
let the random variable be given by
- 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 .

- can thus be regarded as realizations of independent and
-distributed random variables where

**Example**-
*(geometric distribution)*- We consider the following values for and the corresponding
probabilities .
- Let for
, and for , let
- Then, for all ,

and .

- Let for
, and for , let
- Furthermore, we consider the random variable

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

- Then
for all
, i.e.
Geo,

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

- We consider the following values for and the corresponding
probabilities .

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

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

- If we consider the random variable
, formula (11) for the
distribution function of the Erlang-distribution yields for all
- The pseudo-random numbers
where

and

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.

- If is a small number, then the following procedure is
appropriate to generate Poisson-distributed pseudo-random
numbers
*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

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

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

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

- If is large, and
for
,
*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

- For arbitrary but fixed numbers
and where
let
- 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 .

- For the generation of binomially distributed pseudo-random
numbers one can proceed similarly to the Poisson case.