Next: Statistical Tests Up: Generation of Pseudo-Random Numbers Previous: Simple Applications; Monte-Carlo Estimators   Contents

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

 (1)

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

 (2)

yields the standard pseudo-random numbers .

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 .

Theorem 3.1   For all

 (3)

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

 (4)

• 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

where the sequence is generated.
• A desirable feature for the period length of linear congruence generators is to be as close as possible to the maximum length .

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

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

Next: Statistical Tests Up: Generation of Pseudo-Random Numbers Previous: Simple Applications; Monte-Carlo Estimators   Contents
Ursa Pantle 2006-07-20