Spektraltest

Der Spektraltest ist eine Methode, mit der überprüft werden kann, ob gegebene Zufallszahlen tatsächlich stochastisch voneinander unabhängig sind, oder ob das Gegenteil der Fall ist, d. h. bereits „gewürfelte“ Werte die folgenden Werte beeinflussen – und letztere somit (mehr oder minder) vorhersagbar werden.

Für den Spektraltest werden jeweils i gewonnene Zufallszahlen zu i-Tupeln zusammengefasst und überprüft, wie gut sich diese Vektoren in ihrem Wertebereich des i-dimensionalen Raumes verteilen und wie gut diese Verteilung der theoretisch geforderten entspricht.

Anwendung findet der Test bei der Bewertung von (Pseudo-)Zufallszahlengeneratoren. Noch immer häufig verwendet werden beispielsweise lineare Kongruenzgeneratoren (LKG), die je nach Wahl der Parameter sehr unterschiedlich gut bzw. schlecht sind. Ein wesentlich besserer Generator ist etwa der Mersenne-Twister. Eine Alternative zu Generatoren wäre die Messung physikalischer Phänomene (Radioaktivität, echter Würfel).

Grundidee

Mit RANDU generierte Zufallszahlen-Tripel sind nicht zufällig verteilt, sondern konzentrieren sich sämtlich in einer kleinen Anzahl Flächen.

Die Abbildung rechts visualisiert die mit dem RANDU-Algorithmus generierten Zufallszahlen auf eine, der Grundidee des Spektraltests entsprechenden, Art und Weise: Jeweils 3 Zufallszahlen wurden zu einem 3-Tupel (Tripel) zusammengefasst, welches man als Punkt im 3-dimensionalen Raum interpretiert und grafisch darstellt. Der Algorithmus sollte eigentlich gleichverteilte Zufallszahlen erzeugen (im Sinne von: gleichmäßig verteilt). Da ein Tripel von 3 gleichverteilten Zufallsvariablen wieder gleichverteilt ist, würde man in der Grafik eine völlig einförmige Verteilung erwarten.

Es ist jedoch gut zu erkennen, dass diese Punkte ganz und gar nicht gleichmäßig verteilt sind, sondern einem Muster folgen! Kennt man nun bspw. zwei aufeinanderfolgende Zahlen, ist die dritte nicht mehr zufällig, sondern nimmt einen von höchstens 15 verschiedenen Werten an, wodurch man eine 7% Chance hat, den richtigen zu erraten.

Für einen guten Zufallsgenerator sollten es jedoch nicht nur 15 Werte sein, sondern so viele wie möglich. Eine obere Grenze setzt hier die Anzahl m der vom Generator erzeugbaren Zahlen. Werden diese Zahlen gleichmäßig über den gesamten Raum möglicher Tupel (ein Würfel mit Kantenlänge m) verteilt, bekommt man etwa $\sqrt[i]{m}$ Punkte entlang jeder Raumrichtung. Für den abgebildeten 3-dimensionalen Test von RANDU ergibt dies $\sqrt[3]{2^{31}} \approx 1290$. Die tatsächliche Zahl von 15 bleibt also weit hinter dem theoretisch Möglichen zurück!

Durchführung

Für die mathematische bzw. rechnerische Analyse betrachtet man Familien aus parallelen, (Hyper-) Ebenen, die alle denselben Abstand haben und sämtliche Tupel enthalten (für ein bestimmtes i). Es wird dann die Familie mit dem größten Abstand ausgewählt. Dieser Abstand wird mit 1 / ν_i bezeichnet. Der Kehrwert ν_i wird Accuracy genannt. Mathematisch ist es nicht exakt, aber grob kann man ihn sich die Accuracy wieder als ungefähre „Anzahl der Flächen“ vorstellen.

i bezeichnet weiterhin die Länge der untersuchten Tupel bzw. Sequenzen. Für das RANDU-Beispiel haben wir bisher den Fall i = 3 betrachtet, anschaulich: Punkte in einem Würfel, die sich in parallelen Flächen anordnen. 1 / ν₃ bezeichnet den Abstand zwischen diesen Flächen. 2-Tupel hingegen sind Punkte in der Ebene, die sich in parallelen Linien anordnen können. 1 / ν₂ bezeichnet den Abstand zwischen diesen Linien. Die für i = 2 und i = 3 verwendeten geometrischen Konzepte sind für 4 und mehr Dimensionen nicht mehr anschaulich – die verwendete Mathematik lässt sich dennoch problemlos weiterverwenden.

Je größer die Accuracy ν_i, also je kleiner 1 / ν_i ist, umso besser sind die Vektoren in ihrem Wertebereich verteilt. Um die Qualität eines Zufallsgenerators zu beurteilen, berechnet man die ν_i für i von 2 bis vielleicht 5 oder 6 und vergleicht die Ergebnisse mit denen anderer zur Verfügung stehender Generatoren oder dem theoretischen Wert von zirka $\sqrt[i]{m}$.

Die praktische Schwierigkeit besteht darin, einen Algorithmus zu finden, der die benötigte Familie mit dem größten Abstand findet. Für manche Generatoren (z. B. LKGs wie RANDU) existieren Algorithmen, die das exakte Ergebnis mit relativ geringem Rechenaufwand liefern. Ein allgemeinerer Ansatz ist, die Verteilung der Punkte im Raum als Dichte zu interpretieren. Periodische Veränderungen entsprechen dann (i-dimensionalen) Wellen, was eine Analyse des Frequenzspektrums nahe legt, um Hauptrichtung und Amplitude der Wellenfronten zu ermitteln. Daher auch der Name: Spektraltest.

Bei Generatoren, die nur endlich viele verschiedene Zahlen liefern (periodische Generatoren), kann der Test über die gesamte Periode durchgeführt werden.

Beispiele

Die folgenden Beispiele sind lineare Kongruenzgeneratoren. Sie generieren Zufallszahlen mittels der Formel $x_{n+1} = (a \cdot x_n + c) \, \textrm{ mod } \, m$ und festen Konstanten a, c, m sowie dem Startwert x₀. Für diese gibt Knuth^[1] einen konkreten Algorithmus zur Durchführung des Spektraltests an. Die Werte in den Tabellen sind ebenfalls von dort.

Beispiel 1

m = 10000000000 = 10¹⁰; a = 3141592621; c = 1; x₀ = 0. Der Spektraltest liefert

ν2	ν3	ν4	ν5	ν6	ν7
67654	1017	249	42	23	23

Der Generator wurde hier als Beispiel ausgewählt, weil er ein für viele gute Generatoren typisches Ergebnis liefert.

Die Zahlen sagen direkt etwas über die Genauigkeit der erhaltenen Zufallszahlen aus: Wenn man in einer Rechnung immer zwei Zufallszahlen benötigt, etwa weil man Zufallspunkte in der Ebene benötigt, kann man die Ergebnisse maximal mit einer Genauigkeit von 1 / ν₂ = 1 / 67654 = 0.0000148 < 10 ^{− 4} = 4 Dezimalstellen angeben. Wenn man drei pro Rechnung benötigt sind das 1 / ν₃ = 1 / 1017 = 0.000938 < 10 ^{− 3} = 3 Dezimalstellen. Bei vier pro Rechnung ergibt sich 1 / ν₄ = 1 / 249 = 0.00402 < 10 ^{− 2} = 2 Dezimalstellen.

Die Box-Muller-Methode zur Generierung von normalverteilten Zufallszahlen benötigt pro Auswertung zwei Zufallszahlen. Ihre Ergebnisse sind also mit diesem Zufallsgenerator besser als vierstellig. Der im Beispiel verwendete Generator ist brauchbar. Es gibt zwar bessere Generatoren, aber auch viel schlechtere, wie das nächste Beispiel zeigt.

Beispiel 2 – RANDU

Das Horrorbeispiel in diesem Zusammenhang ist der früher gern verwendete Generator RANDU^[2]:

m = 2147483648 = 2³¹; a = 65539 = 2¹⁶+3; c = 0; x₀ = 0 und dem Spektraltestergebnis

ν2	ν3	ν4	ν5	ν6	ν7	ν8	ν9
23171	10	10

Genauer:  $\nu_3 = \sqrt{118} \approx 10;\quad \nu_4 = \ldots = \nu_9 = \sqrt{116} \approx 10$.

Alle i-tupel mit i > 2 haben maximal 1 Dezimalstelle Genauigkeit!

Literatur

• Donald E. Knuth: The Art of Computer Programming. 3. Edition. 23. Printing. Volume 2: Seminumerical Algorithms. Addison-Wesley, Boston MA u. a. 2008, ISBN 978-0-201-89684-8, S. 93ff.

Einzelnachweise

1. ↑ Donald E. Knuth: The Art of Computer Programming. 3. Edition. 23. Printing. Volume 2: Seminumerical Algorithms. Addison-Wesley, Boston MA u. a. 2008, ISBN 978-0-201-89684-8, S. 93ff.
2. ↑ RANDU in der englischsprachigen Wikipedia