Direkt zum Inhalt

Lexikon der Mathematik: Zufallszahlengeneratoren

Rekursionsformeln, nach denen Zahlen, sogenannte Pseudozufallszahlen, erzeugt werden, die sich so verhalten, als wären es Realisierungen einer Zufallsgröße X mit einer bestimmten vorgegebenen Verteilungsfunktion F.

Zufallszahlen werden zumeist zum Testen von Algorithmen in der Numerischen Mathematik, aber auch zum Initialisieren bestimmter Algorithmen (z. B. für Startwerte) verwandt.

Die Generierung wirklich zufälliger Zahlenfolgen durch ein deterministisches Verfahren ist prinzipiell unmöglich. Die Unzulänglichkeit der Methoden besteht darin, daß der Vorrat so erzeugter Pseudozufallszahlen beschränkt ist; man kann zeigen, daß jede Folge von Zahlen, die gemäß einer rekursiven Vorschrift berechnet wird, periodisch ist, sich also nach einer gewissen Anzahl p (der Periode) von Iterationsschritten wiederholt. Bei den meisten heutzutage verwendeten Zufallszahlengeneratoren ist p allerdings so groß, daß der Generator für beliebige praktische Erfordernisse ausreicht.

Die Erzeugung von Pseudozufallszahlen erfolgt in drei Schritten:

Schritt 1: Erzeugung von ganzzahligen in einer Menge {0, 1, …, m − 1} gleichverteilten Zufallszahlen. Die gebräuchlichste Methode ist hier die sogenannte Lineare Kongruenzmethode. Ausgehend von einem Startwert x0 werden die Zahlen gemäß der rekursiven Beziehung \begin{eqnarray}{x}_{i}=(a{x}_{i-1}+b)\,\,\,\mathrm{mod}\,\,(m),i=1,2,\ldots \end{eqnarray} erzeugt. Die Periode p des Generators ist offensichtlich höchstens gleich m. Die Konstanten a, b und m sowie der Startwert x0 müssen so gewählt werden, daß möglichst die volle Periodenlänge p = m erreicht wird. Verschiedene andere Varianten von Zufallszahlengeneratoren, die auf der linearen Kongruenzmethode beruhen, sind z. B. die Regeln \begin{eqnarray}\begin{array}{l}{x}_{i}=(a{x}_{i-1}+b)\,\,\,\mathrm{mod}\,\,(m),i=1,2,\ldots \\ {x}_{i}=(a{x}_{i-1}+b{x}_{i-2}+c{x}_{i-3}+d)\,\,\,\mathrm{mod}\,\,(m),i=3,4,\ldots\end{array}\end{eqnarray} die als Lineare Kongruenzmethode 2. bzw. 3. Ordnung bezeichnet werden. In [1] werden Werte für die Konstanten a, b, c, d, m dieser drei Generatoren empfohlen, die für beliebige Startwerte ungleich 0 die volle Periodenlänge m erreichen.

Schritt 2: Erzeugung auf dem Intervall [0, 1] stetig gleichverteilter Zufallszahlen. Diese erhält man aus den in Schritt 1 erzeugten Zahlen gemäß der Vorschrift zi = xi/(m − 1).

Schritt 3: Erzeugung von Zufallszahlen, die einer vorgegebenen Verteilung F genügen.

Diskrete Verteilungen: Die Erzeugung von Zufallszahlen y, die der diskreten Verteilung pi = P(Y = ai), i = 1, …, k, genügen erfolgt gemäß der Vorschrift:

  1. Erzeuge eine auf [0,1] gleichverteilte Zahl z gemäß 2)
  2. Definiere \begin{eqnarray}y={a}_{i},\,\text{falls}\,{h}_{i-1}\le z\lt {h}_{i},i=1,2,\ldots,k\end{eqnarray} wobei \begin{eqnarray}{h}_{0}=0\,\text{und}\,{h}_{i}={\sum }_{j=1}^{i}{p}_{j},i=1,\ldots,k\end{eqnarray} die kumulierten Wahrscheinlichkeiten sind (vgl. Abb. 1).

Stetige Verteilungen: Die gebräuchlichste Methode zur Erzeugung von Zufallszahlen y, die sich verhalten, als wären es Realisierungen einer Zufallsgröße Y mit der stetigen Verteilungsfunktion F, ist die sogenannte inverse Transformation. Sie ist die direkte Verallgemeinerung des Vorgehens im diskreten Fall (vgl. Abb. 2) und basiert auf folgendem Satz:

Y = F−1(Z) besitzt die Verteilungsfunktion F genau dann, wenn Z eine auf [0, 1] stetig gleichverteilte Zufallsgröße ist.

Wir erzeugen also eine Realisierung y von Y wie folgt:

  1. Erzeuge eine in [0, 1] gleichverteilte Zufallszahl z gemäß 2)
  2. Setze y = F−1(z), d. h., löse die Gleichung z = F(y) nach y auf.

Abbildung 1 zum Lexikonartikel Zufallszahlengeneratoren
© Springer-Verlag GmbH Deutschland 2017
 Bild vergrößern

Abbildung 1: Erzeugung diskret verteilter Zufallszahlen

Ein Beispiel: Die Erzeugung einer Weibull-verteil-ten (Weibull-Verteilung) Zufallsgröße mit den Parametern α und λ erfolgt nach der Vorschrift \begin{eqnarray}y={F}^{-1}(z)=\exp\,\left(\frac{1}{\alpha }\mathrm{ln}\,\left(-\frac{1}{\text{λ}}\mathrm{ln}\,(1-z)\right)\right)\end{eqnarray} Für die Erzeugung normalverteilter Zufallszahlen sind spezielle Generatoren entwickelt worden, da im Falle der Normalverteilung die inverse Verteilungsfunktion F−1 nicht analytisch berechenbar ist. Nach Box und Müller lassen sich zwei standard-normalverteilte Zufallszahlen y1 und y2 gemäß folgender Vorschrift aus zwei auf [0, 1] gleichverteilten Zufallszahlen z1 und z2 erzeugen: \begin{eqnarray}{y}_{1}=\sqrt{-2\mathrm{ln}({z}_{1})}\cos (2\pi {z}_{2}),\end{eqnarray}\begin{eqnarray}{y}_{2}=\sqrt{-2\mathrm{ln}({z}_{1})}\sin (2\pi {z}_{2}).\end{eqnarray}

Abbildung 2 zum Lexikonartikel Zufallszahlengeneratoren
© Springer-Verlag GmbH Deutschland 2017
 Bild vergrößern

Abbildung 2: Erzeugung stetig verteilter Zufallszahlen durch inverse Transformation

Eine andere Methode zur Erzeugung näherungsweise standardnormalverteilter Zufallsgrößen basiert auf dem Zentralen Grenzwertsatz: Aus einer standardnormalverteilten Zufallszahl y erhält man gemäß der Vorschrift y* = σy + μ eine gemäß N(μ, σ2) normalverteilte Zufallszahl y*.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos