28 - Erzeugung von Zufallszahlen

Gemischter linearer Kongruenzoperator

Der gemischte lineare Kongruenzoperator erzeugt Zufallszahlen mit maximaler Periodenlänge $m$, die annähernd $U[0,1]$-verteilt sind:

Wähle einen Startwert $y_1\in\{0,\ldots,m-1\}$!
Berechne die Folge $$y_i=(ay_{i-1}+b)\mod m$$ mit $a,b\in\{1,\ldots,m-1\}$!
Gebe $y_i/m$ aus!

Gute Resultate erhält man für $m=2^{35}$, $a=2^7+1$ und $b=0$.
Für kryptografische Zwecke ist diese Methode nicht sicher genug.

Inversionsmethode

Ist $U\sim U[0,1]$, dann hat die Zufallsvariable $X=F^{-1}(U)$ die Verteilungsfunktion $F(x)$.

Poissonverteilte Zufallszahlen

Sind $Y_1,\ldots,Y_n\sim\text{Exp}(1)$ unabhängig, dann ist die Zahl $X\geq0$ mit $$\sum_{i=1}^X\,Y_i<\lambda\leq\sum_{i=1}^{X+1}Y_i$$ poissonverteilt mit Erwartungswert $\lambda$.

Box-Muller-Methode

Sind die beiden Zufallsvariablen $U_1$ und $U_2$ unabhängig und identisch $U[0,1]$-verteilt, dann sind $Z_1=\sqrt{-2\ln U_1}\cos(2\pi U_2)$ und $Z_2=\sqrt{-2\ln U_1}\sin(2\pi U_2)$ unabhängig und identisch $N(0,1)$-verteilt.