Lineare Kongruenzgeneratoren

• Den Ausgangspunkt der meisten Simulationsalgorithmen bilden Standard-Zufallszahlen-Generatoren,
  • deren Ziel darin besteht, Folgen $u_1,\ldots,u_n$ von Zahlen aus dem Einheitsintervall $(0,1]$ zu erzeugen, sogenannte Standard-Pseudozufallszahlen,
  • die als Realisierungen von unabhängigen und (identisch in $(0,1]$) gleichverteilten Zufallsvariablen $U_1,\ldots,U_n$ aufgefasst werden können.
• Ein weit verbreitetes Verfahren zur Erzeugung von Standard-Pseudozufallszahlen ist die folgende lineare Kongruenzmethode,
  • wobei zunächst die Zahlen $z_1,\ldots,z_n$ gemäß einer Rekursion vom Typ

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

    
    
    erzeugt werden.
  • Dabei wird von einem gewissen Startwert $z_0\in\{0,1,\ldots,m-1\}$ ausgegangen, der auch Keim des linearen Kongruenzgenerators genannt wird, und
  • $m\in\mathbb{N}$, $a\in\{0,1,\ldots,m-1\}$ bzw. $c\in\{0,1,\ldots,m-1\}$ sind weitere Parameter, die Modul, Faktor bzw. Inkrement des Kongruenzgenerators genannt werden.
  • Hieraus ergeben sich durch die Normierung

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

    
    
    die Standard-Pseudozufallszahlen $u_1,\ldots,u_n$.

Wir lösen nun die Rekursionsgleichung (1), d.h., wir zeigen, wie sich die in (1) rekursiv definierte Zahl $z_k$ direkt durch den Startwert $z_0$ sowie durch die Parameter $m$, $a$ bzw. $c$ ausdrücken lässt.

Theorem 3.1   $\;$ Für jedes $k\in\{1,\ldots,n\}$ gilt

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

Beweis

 

• Wir führen den Beweis mit vollständiger Induktion, wobei für $k=1$ die Behauptung (3) identisch ist mit der Rekursionsgleichung (1).
• Es gelte (3) nun für eine gewisse natürliche Zahl $k\ge 1$, d.h., es gibt eine ganze Zahl $j\ge 0$, so dass

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

  
  

• Wir zeigen, dass dann (3) auch für $k+1$ gilt.
• Aus der Rekursionsgleichung (1) und aus der Induktionsannahme (4) ergibt sich, dass
  

  $$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)\,.$$

  
  

• Damit ist die Gültigkeit von (3) für $k+1$ bewiesen.
  
  $\Box$

Beachte

 

• Es ist klar, dass mit dem in (1) definierten linearen Kongruenzgenerator höchstens $m$ verschiedene Zahlen $z_1,\ldots,z_n$ erzeugt werden können.
  • Sobald sich eine Zahl $z_k$ zum ersten Mal wiederholt, d.h., es gibt ein $m_0>0$ mit $z_k=z_{k-m_0}$,
  • dann beginnt erneut die gleiche Periode der Länge $m_0$, die bereits einmal vollständig erzeugt worden ist, d.h., es gilt
    $$z_{k+j}=z_{k-m_0+j}$$   $$\mbox{für jedes $j\ge 1$.}$$$$$$

• Bei einer ungünstigen Wahl der Parameter $m$, $a$, $c$ bzw. $z_0$ kann die Länge der Periode $m_0$ sehr klein sein.
  • Beispielsweise gilt
    $$m_0=2$$   $$\mbox{für $a=c=z_0=5$\ und $m=10$,}$$$$$$
    wobei dann lediglich die Zahlen $5,0,5,0,\ldots$ generiert werden.
  • Ein wünschenswertes Qualitätskriterium von linearen Kongruenzgeneratoren ist jedoch, dass die Länge der Periode $m_0$ möglichst nahe bei der Maximallänge $m$ liegt.

Wir erwähnen nun (hinreichende und notwendige) Bedingungen an die Parameter $m$, $a$, $c$ bzw. $z_0$, die insbesondere sichern, dass die maximal mögliche Periode $m$ erreicht wird.

Theorem 3.2    

1.

Falls $c>0$, so erzeugt der in $(\ref{def.lin.kon})$ definierte lineare Kongruenzgenerator genau dann für jeden Startwert $z_0\in\{0,1,\ldots,m-1\}$ eine Zahlenfolge $z_1,\ldots,z_n$ mit der maximal möglichen Periode $m$, wenn die folgenden Bedingungen erfüllt sind:

(a$_1$)

Die Parameter $c$ und $m$ sind teilerfremd.

(a$_2$)

Für jede Primzahl $r$, die $m$ teilt, ist $a-1$ ein Vielfaches von $r$.

(a$_3$)

Falls $m$ ein Vielfaches von $4$ ist, dann ist auch $a-1$ ein Vielfaches von $4$.

2.

Falls $c=0$, so gilt $m_0=m-1$ für jedes $z_0\in\{1,\ldots,m-1\}$ genau dann, wenn

(b$_1$)

$m$ eine Primzahl ist,

(b$_2$)

für jede Primzahl $r$, die $m-1$ teilt, die Zahl $a^{(m-1)/r}-1$ nicht durch $m$ teilbar ist.

3.

Falls $c=0$ und falls es ein $k\in\mathbb{N}$ mit $m=2^k\ge 16$ gibt, so gilt $m_0=m/4$ genau dann, wenn $z_0$ eine ungerade Zahl ist und wenn $a\mod(8)=5$ oder $=3$ gilt.

• Einen Beweis von Theorem 3.2, in dem Ergebnisse der Zahlentheorie (u.a. der kleine Satz von Fermat) verwendet werden, kann man beispielsweise
  • in Abschnitt 2.7 des Buches von B.D. Ripley (1987) Stochastic Simulation, J. Wiley & Sons, New York oder
  • in Abschnitt 3.2 von D.E. Knuth (1997) The Art of Computer Programming, Vol. II, Addison-Wesley, Reading MA finden.

• Darüber hinaus verweisen wir auch auf diese beiden Bücher hinsichtlich der Diskussion
  • von anderen Generatoren zur Erzeugung von Standard-Pseudozufallszahlen wie beispielsweise nichtlineare Kongruenzgeneratoren, Schieberegister-Generatoren, Lagged-Fibonacci-Generatoren sowie die Kombination solcher Generatoren,
  • von alternativen Bedingungen an die Parameter $m$, $a$, $c$ bzw. $z_0$ des linearen Kongruenzgenerators, der in (1) definiert wurde,
  • um Zahlenfolgen $z_1,\ldots,z_n$ mit einer möglichst großen Periode $m_0$ und mit weiteren Güteeigenschaften zu erzeugen.
• Eine solche Güteeigenschaft besteht darin,
  • dass die Punkte $(u_1,u_2),\ldots,(u_{n-1},u_n)$ von jeweils aufeinanderfolgenden Pseudozufallszahlen $u_{i-1}$, $u_i$ das Einheitsquadrat $[0,1]^2$ möglichst gleichmäßig ausfüllen,
  • wobei die folgenden Zahlenbeispiele verdeutlichen, dass relativ geringfügige Änderungen der Parameter $a$ und $c$ zu völlig unterschiedlichen Punktmustern $(u_1,u_2),\ldots(u_{n-1},u_n)$ führen können.
• Weitere Details hierzu sind beispielsweise in dem bereits erwähnten Buch von Ripley (1987) bzw. in dem Vorlesungsskipt von H. Künsch unter ftp://stat.ethz.ch/U/Kuensch/skript-sim.ps zu finden, wo auch die folgenden Abbildungen enthalten sind.

Abbildung: Punktmuster für Paare $(u_{i-1},u_i)$ aufeinanderfolgender Pseudozufallszahlen mit $m=256$

Abbildung: Punktmuster für Paare $(u_{i-1},u_i)$ aufeinanderfolgender Pseudozufallszahlen mit $m=256$

Abbildung: Punktmuster für Paare $(u_{i-1},u_i)$ aufeinanderfolgender Pseudozufallszahlen mit $m=2048$