Spektraltest

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten]

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 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 m der vom Generator erzeugbaren Zahlen. Werden diese Zahlen gleichmäßig über den gesamten Raum möglicher Tupel (einen Würfel mit Kantenlänge m) verteilt, bekommt man etwa \sqrt[i]{m} Punkte entlang jeder Raumrichtung. Für den abgebildeten dreidimensionalen 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[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 i). Es wird dann die Familie mit dem größten Abstand ausgewählt. Dieser Abstand wird mit 1/\nu_i bezeichnet. Der Kehrwert \nu_i wird Accuracy genannt. Mathematisch ist es nicht exakt, aber grob kann man 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/\nu_3 bezeichnet den Abstand zwischen diesen Flächen. 2-Tupel hingegen sind Punkte in der Ebene, die sich in parallelen Linien anordnen können. 1/\nu_2 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 \nu_i, also je kleiner 1/\nu_i ist, umso besser sind die Vektoren in ihrem Wertebereich verteilt. Um die Qualität eines Zufallsgenerators zu beurteilen, berechnet man die \nu_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 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 x_{n+1} = (a \cdot x_n + c) \, \textrm{ mod } \, m und festen Konstanten a, c, m sowie dem Startwert x0. 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[Bearbeiten]

m = 10000000000 = 1010; a = 3141592621; c = 1; x0 = 0. Der Spektraltest liefert

\nu_2 \nu_3 \nu_4 \nu_5 \nu_6 \nu_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/\nu_2 = 1/67654 = 0.0000148 < 10^{-4} = 4 Dezimalstellen angeben. Wenn man drei pro Rechnung benötigt sind das 1/\nu_3 = 1/1017 = 0.000938 < 10^{-3} = 3 Dezimalstellen. Bei vier pro Rechnung ergibt sich 1/\nu_4 = 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[Bearbeiten]

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

m = 2147483648 = 231; a = 65539 = 216+3; c = 0; x0 = 1 und dem Spektraltestergebnis

\nu_2 \nu_3 \nu_4 \nu_5 \nu_6 \nu_7 \nu_8 \nu_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[Bearbeiten]

Einzelnachweise[Bearbeiten]

  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