Linear Congruential Generators

- Most simulation algorithms are based on
*standard random number generators*,- whose goal is to generate sequences
of numbers in
the unit interval . These are the so-called
*standard pseudo-random numbers*, - which can be regarded as realizations of independent and on uniformly distributed random variables .

- whose goal is to generate sequences
of numbers in
the unit interval . These are the so-called
- A commonly established procedure to generate standard pseudo-random
numbers is the following
*linear congruential method*,- where first of all the numbers
are generated
according to a recursion formula

. - The initial value
the algorithm is
starting from is called
*germ*of the linear congruential generator. -
,
and
are
further parameters called
*modulus*,*factor*and*increment*of the congruential generator. - The scaling

yields the standard pseudo-random numbers .

- where first of all the numbers
are generated
according to a recursion formula

As a next step we will solve the recursion equation
(1), i.e., we will show how the number that
has been recursively defined in (1) can be
expressed *directly* by the initial value and the
parameters , and .

**Proof**-
- We show the assertion by mathematical induction. For the claim (3) coincides with the recursion equation (1).
- Let (3) be true for a certain , i.e.,
there is an integer such that

- We show that this implies that (3) also holds for .
- By the recursion equation (1) and by induction
hypothesis (4) we get that

i.e., (3) also holds for .

**Remarks**-
- Obviously, the linear congruential generator defined in
(1) can generate no more than different numbers
.
- As soon as a number is repeated for the first time, i.e., there is some such that ,
- the same period of length , which has already been completely
generated, is started again, i.e.

- An unfavorable choice of the parameters , , and ,
respectively, may result in a very short length of the
period.
- For example we have
- A desirable feature for the period length of linear
congruence generators is to be as close as possible to the maximum
length .

- For example we have

- Obviously, the linear congruential generator defined in
(1) can generate no more than different numbers
.

We will now mention some (sufficient and necessary) conditions for the parameters , , and , respectively, ensuring that the maximal possible period is obtained.

- 1.
- If , then for every initial value
the linear congruential
generator defined in
generates
a sequence
of numbers with maximal possible period if and only if
the following conditions are satisfied:
- (a)
- The parameters and are relatively prime.
- (a)
- For every prime number dividing , is a multiple of .
- (a)
- If is a multiple of then also is multiple of .

- 2.
- If then for all
if and only
if
- (b)
- is prime and
- (b)
- for any prime dividing the number is not divisible by .

- 3.
- If and if there is such that then if and only if is an odd number and or gilt.

A *proof* of Theorem 3.2 using results from
number theory (one of them being Fermat's little theorem) can be
found e.g.

- in Section 2.7 of B.D. Ripley
*Stochastic Simulation*, J. Wiley & Sons, New York (1987) or - in Section 3.2 of D.E. Knuth (1997)
*The Art of Computer Programming*, Vol. II, Addison-Wesley, Reading MA.

- We also refer to these two texts for the discussion
- of other generators for standard pseudo-random numbers like nonlinear congruential generators, shift-register generators and lagged Fibonacci generators as well as their combinations,
- alternative conditions for the parameters , , and of the linear congruential generator defined in (1),
- ensuring the generation of sequences whose period is as large as possible and also exhibiting other desirable properties.

- One of those properties is
- that the points formed by pairs of consecutive pseudo-random numbers , are uniformly spread over the unit square .
- The following numerical examples illustrate that relatively small
changes of the parameters and can result in completely
different
*point patterns*.

- Further details can be found in the text by Ripley (1987) that has been already mentioned and in the lecture notes by H. Künsch (ftp://stat.ethz.ch/U/Kuensch/skript-sim.ps) that also contains the following figures.