Linear Congruential Generators

• Most simulation algorithms are based on standard random number generators,
  • whose goal is to generate sequences $u_1,\ldots,u_n$ of numbers in the unit interval $(0,1]$. These are the so-called standard pseudo-random numbers,
  • which can be regarded as realizations of independent and on $(0,1]$ uniformly distributed random variables $U_1,\ldots,U_n$.
• A commonly established procedure to generate standard pseudo-random numbers is the following linear congruential method,
  • where first of all the numbers $z_1,\ldots,z_n$ are generated according to a recursion formula

    $$z_k=(a z_{k-1}+c)\mod (m) \,,\qquad\forall\, k=1,\ldots,n$$ (1)

    
    
    .
  • The initial value $z_0\in\{0,1,\ldots,m-1\}$ the algorithm is starting from is called germ of the linear congruential generator.
  • $m\in\mathbb{N}$, $a\in\{0,1,\ldots,m-1\}$ and $c\in\{0,1,\ldots,m-1\}$ are further parameters called modulus, factor and increment of the congruential generator.
  • The scaling

    $$u_k=\frac{z_k}{m}$$ (2)

    
    
    yields the standard pseudo-random numbers $u_1,\ldots,u_n$.

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

Theorem 3.1   $\;$ For all $k\in\{1,\ldots,n\}$

$$z_k=\Bigl(a^k z_0+c\;\frac{a^k-1}{a-1}\Bigr)\,\mod (m)\,.$$ (3)

Proof

 

• We show the assertion by mathematical induction. For $k=1$ the claim (3) coincides with the recursion equation (1).
• Let (3) be true for a certain $k\ge 1$, i.e., there is an integer $j\ge 0$ such that

  $$z_k=a^k z_0+c\;\frac{a^k-1}{a-1}\;-jm\,.$$ (4)

  
  

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

  $$z_{k+1} = (a z_k+c)\mod (m)$$

  $$= \Biggl(a\Bigl(a^k z_0+c\;\frac{a^k-1}{a-1}\;-jm\Bigr)+c\Biggr)\mod (m)$$

  $$= \Bigl(a^{k+1} z_0+c\;\frac{a(a^k-1)+a-1}{a-1}\;-ajm\Bigr) \mod (m)$$

  $$= \Bigl(a^{k+1} z_0+c\;\frac{a^{k+1}-1}{a-1}\Bigr) \mod (m)\,,$$

  
  
  i.e., (3) also holds for $k+1$.
  
  $\Box$

Remarks

 

• Obviously, the linear congruential generator defined in (1) can generate no more than $m$ different numbers $z_1,\ldots,z_n$.
  • As soon as a number $z_k$ is repeated for the first time, i.e., there is some $m_0>0$ such that $z_k=z_{k-m_0}$,
  • the same period of length $m_0$, which has already been completely generated, is started again, i.e.
    $$z_{k+j}=z_{k-m_0+j}$$   $$\mbox{for all $j\ge 1$.}$$$$$$

• An unfavorable choice of the parameters $m$, $a$, $c$ and $z_0$, respectively, may result in a very short length $m_0$ of the period.
  • For example we have
    $$m_0=2$$   $$\mbox{for $a=c=z_0=5$\ and $m=10$,}$$$$$$
    where the sequence $5,0,5,0,\ldots$ is generated.
  • A desirable feature for the period length $m_0$ of linear congruence generators is to be as close as possible to the maximum length $m$.

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

Theorem 3.2    

1.

If $c>0$, then for every initial value $z_0\in\{0,1,\ldots,m-1\}$ the linear congruential generator defined in $(\ref{def.lin.kon})$ generates a sequence $z_1,\ldots,z_n$ of numbers with maximal possible period $m$ if and only if the following conditions are satisfied:

(a$_1$)

The parameters $c$ and $m$ are relatively prime.

(a$_2$)

For every prime number $r$ dividing $m$, $a-1$ is a multiple of $r$.

(a$_3$)

If $m$ is a multiple of $4$ then also $a-1$ is multiple of $4$.

2.

If $c=0$ then $m_0=m-1$ for all $z_0\in\{1,\ldots,m-1\}$ if and only if

(b$_1$)

$m$ is prime and

(b$_2$)

for any prime $r$ dividing $m-1$ the number $a^{(m-1)/r}-1$ is not divisible by $m$.

3.

If $c=0$ and if there is $k\in\mathbb{N}$ such that $m=2^k\ge 16$ then $m_0=m/4$ if and only if $z_0$ is an odd number and $a\mod(8)=5$ or $=3$ 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 $m$, $a$, $c$ and $z_0$ of the linear congruential generator defined in (1),
  • ensuring the generation of sequences $z_1,\ldots,z_n$ whose period $m_0$ is as large as possible and also exhibiting other desirable properties.
• One of those properties is
  • that the points $(u_1,u_2),\ldots,(u_{n-1},u_n)$ formed by pairs of consecutive pseudo-random numbers $u_{i-1}$, $u_i$ are uniformly spread over the unit square $[0,1]^2$.
  • The following numerical examples illustrate that relatively small changes of the parameters $a$ and $c$ can result in completely different point patterns $(u_1,u_2),\ldots(u_{n-1},u_n)$.
• 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.

Figure 3: Point patterns for pairs $(u_{i-1},u_i)$ of consecutive pseudo-random numbers for $m=256$

Figure 4: Point patterns for pairs $(u_{i-1},u_i)$ of consecutive pseudo-random numbers for $m=256$

Figure 5: Point patterns for pairs $(u_{i-1},u_i)$ of consecutive pseudo-random numbers for $m=2048$