Satz von Marsaglia

Der Satz von Marsaglia (nach George Marsaglia, 1968) besagt für die aus einem linearen Kongruenzgenerator ${\displaystyle y_{i+1}\equiv (ay_{i}+r)\,{\bmod {\,}}m}$ (siehe dort) gewonnenen Pseudozufallszahlen ${\displaystyle u_{i}={\frac {y_{i}}{m}}}$ Folgendes:

Bildet man aus der Folge ${\displaystyle (u_{i})_{i\geq 0}}$ die Tupel ${\displaystyle (u_{0},...,u_{k-1})}$, ${\displaystyle (u_{1},...,u_{k})}$, ..., ${\displaystyle (u_{n+1},...,u_{n+k})}$, ..., so liegen die durch diese ${\displaystyle k}$-Tupel bestimmten Punkte im ${\displaystyle \mathbb {R} ^{k}}$ auf maximal ${\displaystyle {\sqrt[{k}]{m\cdot k!}}}$ parallelen Hyperebenen.

Hierbei verwendet man folgende Komponenten:

• Modul ${\displaystyle m\in \mathbb {N} }$,
• Inkrement ${\displaystyle r\in \mathbb {N} _{0}}$,
• Faktor ${\displaystyle a\in \mathbb {Z} }$,
• Startwert (Saat) ${\displaystyle y_{0}\in \left\{0,...,m-1\right\}}$.

Der Satz eignet sich also für das Testen linearer Kongruenzgeneratoren, da bei einer höheren Anzahl paralleler Hyperebenen eine höhere Qualität der Pseudozufallszahlen angenommen werden kann.

Der inverse Kongruenzgenerator kennt ein solches Hyperebenenverhalten nicht und bietet sich daher als Alternative zum linearen Kongruenzgenerator an.

Der Satz von Marsaglia findet beim Spektraltest zum Testen von Zufallszahlen Anwendung.

Literatur

• George Marsaglia: Random numbers fall mainly in the planes. In: Proc Natl Acad Sci U S A. Band 61, Nr. 1, September 1968, S. 25–28, doi:10.1073/pnas.61.1.25.