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 gewonnene Zufallszahlen zu -Tupeln zusammengefasst und überprüft, wie gut sich diese Vektoren in ihrem Wertebereich des -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 Bearbeiten
Abbildung 1 visualisiert die mit dem RANDU-Algorithmus generierten Zufallszahlen auf eine, der Grundidee des Spektraltests entsprechende, Art und Weise: Jeweils drei Zufallszahlen wurden zu einem 3-Tupel (Tripel) zusammengefasst, welches man als Punkt im dreidimensionalen Raum interpretiert und grafisch darstellt. Der Algorithmus sollte eigentlich gleichverteilte Zufallszahlen erzeugen (im Sinne von: gleichmäßig verteilt). Da ein Tripel von drei 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 siebenprozentige 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 der vom Generator erzeugbaren Zahlen. Werden diese Zahlen gleichmäßig über den gesamten Raum möglicher Tupel (einen Würfel mit Kantenlänge ) verteilt, bekommt man etwa Punkte entlang jeder Raumrichtung. Für den abgebildeten dreidimensionalen Test von RANDU ergibt dies . Die tatsächliche Zahl von 15 bleibt also weit hinter dem theoretisch Möglichen zurück.
Durchführung Bearbeiten
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 ). Es wird dann die Familie mit dem größten Abstand ausgewählt. Dieser Abstand wird mit bezeichnet. Der Kehrwert wird Accuracy genannt. Mathematisch ist es nicht exakt, aber grob kann man sich die Accuracy wieder als ungefähre „Anzahl der Flächen“ vorstellen.
bezeichnet weiterhin die Länge der untersuchten Tupel bzw. Sequenzen. Für das RANDU-Beispiel haben wir bisher den Fall betrachtet, anschaulich: Punkte in einem Würfel, die sich in parallelen Flächen anordnen. bezeichnet den Abstand zwischen diesen Flächen. 2-Tupel hingegen sind Punkte in der Ebene, die sich in parallelen Linien anordnen können. bezeichnet den Abstand zwischen diesen Linien. Die für und 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 , also je kleiner ist, umso besser sind die Vektoren in ihrem Wertebereich verteilt. Um die Qualität eines Zufallsgenerators zu beurteilen, berechnet man die 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 .
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 nahelegt, 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 Bearbeiten
Die folgenden Beispiele sind lineare Kongruenzgeneratoren. Sie generieren Zufallszahlen mittels der Formel und festen Konstanten , , sowie dem Startwert x0. Für diese gibt Knuth einen konkreten Algorithmus zur Durchführung des Spektraltests an. Die Werte in den Tabellen sind ebenfalls von dort.
Beispiel 1 Bearbeiten
m = 10000000000 = 1010; a = 3141592621; c = 1; x0 = 0. Der Spektraltest liefert
| 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 angeben. Wenn man drei pro Rechnung benötigt sind das . Bei vier pro Rechnung ergibt sich .
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 Bearbeiten
Das Horrorbeispiel in diesem Zusammenhang ist der früher gern verwendete Generator RANDU:
m = 2147483648 = 231; a = 65539 = 216+3; c = 0; x0 = 1 und dem Spektraltestergebnis
| 23171 | 10 | 10 |
Genauer: .
Alle i-tupel mit i > 2 haben maximal 1 Dezimalstelle Genauigkeit!
Literatur Bearbeiten
- 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.
Weblinks Bearbeiten
Einzelnachweise Bearbeiten
- 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.
- RANDU in der englischsprachigen Wikipedia