Rekursiver arithmetischer Zufallszahlengenerator

Rekursive arithmetische Zufallszahlengeneratoren sind Zufallszahlengeneratoren, die auf arithmetischen Zufallszahlengeneratoren basieren, bei denen man sich jedoch mit bestimmt rationalen Zahlen als Zufallszahlen zufrieden gibt, da irrationale Zahlen, von denen arithmetische Zufallszahlengeneratoren ausgehen, auf Rechnern nicht darstellbar sind.

Zur Initialisierung des Generators verwendet man Startwerte $y_{0},y_{1},...,y_{k-1}$, die als Saat bezeichnet werden.

Eine arithmetische Funktion $f:\left\{0,...,m\right\}^{k}\rightarrow \left\{0,...,m\right\}$ erzeugt nun sukzessive die Werte $y_{n}:=f(y_{n-k},y_{n-k+1},...,y_{n-1}$, wobei $n\geq k$.

Nun verwendet man $u_{i}={\frac {y_{i}}{m}}$ als Zufallszahlen.

Man gibt sich für die Zufallszahlen also mit Werten im Intervall $\left\{0,{\frac {1}{m}},{\frac {2}{m}},...,{\frac {m-1}{m}},1\right\}$ zufrieden, wobei $m$ eine hinreichend große natürliche Zahl ist.

Die wohl bedeutendsten arithmetischen Zufallszahlengeneratoren sind Kongruenzgeneratoren.

Vorteile

Bei geeigneter Funktion $f$ lassen sich schnell Zufallszahlen erzeugen. Diese sind bei Angabe der Saat vollstädnig reproduzierbar.

Nachteile

Die Folge $(y_{n})_{n\geq 0}$ ist deterministisch. Es werden keine echten Zufallszahlen, sondern vielmehr nur Pseudozufallszahlen erzeugt. Es handelt sich also um einen Pseudozufallszahlengenerator. Die Determiniertheit bedingt auch, dass eine Unabhängigkeit und Gleichverteilung der Folge nicht gegeben ist.

Insbesondere wird irgendwann eine Schleife erzeugt. Es gibt also $n_{0},p\in \mathbb {N}$ mit $y_{n+p}=y_{n}$ für alle $n\geq n_{0}$. Das kleinste $p$ bezeichnet man hierbei als Periode.