Spektraltest - LinkFang.de





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 [math]i[/math] gewonnene Zufallszahlen zu [math]i[/math]-Tupeln zusammengefasst und überprüft, wie gut sich diese Vektoren in ihrem Wertebereich des [math]i[/math]-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

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 [math]m[/math] der vom Generator erzeugbaren Zahlen. Werden diese Zahlen gleichmäßig über den gesamten Raum möglicher Tupel (einen Würfel mit Kantenlänge [math]m[/math]) verteilt, bekommt man etwa [math]\sqrt[i]{m}[/math] Punkte entlang jeder Raumrichtung. Für den abgebildeten dreidimensionalen Test von RANDU ergibt dies [math]\sqrt[3]{2^{31}} \approx 1290[/math]. 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 [math]i[/math]). Es wird dann die Familie mit dem größten Abstand ausgewählt. Dieser Abstand wird mit [math]1/\nu_i[/math] bezeichnet. Der Kehrwert [math]\nu_i[/math] wird Accuracy genannt. Mathematisch ist es nicht exakt, aber grob kann man sich die Accuracy wieder als ungefähre „Anzahl der Flächen“ vorstellen.

[math]i[/math] bezeichnet weiterhin die Länge der untersuchten Tupel bzw. Sequenzen. Für das RANDU-Beispiel haben wir bisher den Fall [math]i=3[/math] betrachtet, anschaulich: Punkte in einem Würfel, die sich in parallelen Flächen anordnen. [math]1/\nu_3[/math] bezeichnet den Abstand zwischen diesen Flächen. 2-Tupel hingegen sind Punkte in der Ebene, die sich in parallelen Linien anordnen können. [math]1/\nu_2[/math] bezeichnet den Abstand zwischen diesen Linien. Die für [math]i=2[/math] und [math]i=3[/math] 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 [math]\nu_i[/math], also je kleiner [math]1/\nu_i[/math] ist, umso besser sind die Vektoren in ihrem Wertebereich verteilt. Um die Qualität eines Zufallsgenerators zu beurteilen, berechnet man die [math]\nu_i[/math] 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 [math]\sqrt[i]{m}[/math].

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

Die folgenden Beispiele sind lineare Kongruenzgeneratoren. Sie generieren Zufallszahlen mittels der Formel [math]x_{n+1} = (a \cdot x_n + c) \, \textrm{ mod } \, m[/math] und festen Konstanten [math]a[/math], [math]c[/math], [math]m[/math] 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

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

[math]\nu_2[/math] [math]\nu_3[/math] [math]\nu_4[/math] [math]\nu_5[/math] [math]\nu_6[/math] [math]\nu_7[/math]
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 [math]1/\nu_2 = 1/67654 = 0.0000148 \lt 10^{-4} = 4[/math] Dezimalstellen angeben. Wenn man drei pro Rechnung benötigt sind das [math]1/\nu_3 = 1/1017 = 0.000938 \lt 10^{-3} = 3[/math] Dezimalstellen. Bei vier pro Rechnung ergibt sich [math]1/\nu_4 = 1/249 = 0.00402 \lt 10^{-2} = 2[/math] 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 = 231; a = 65539 = 216+3; c = 0; x0 = 1 und dem Spektraltestergebnis

[math]\nu_2[/math] [math]\nu_3[/math] [math]\nu_4[/math] [math]\nu_5[/math] [math]\nu_6[/math] [math]\nu_7[/math] [math]\nu_8[/math] [math]\nu_9[/math]
23171 10 10

Genauer:  [math]\nu_3 = \sqrt{118} \approx 10;\quad \nu_4 = \ldots = \nu_9 = \sqrt{116} \approx 10[/math].

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

Literatur

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

Kategorien: Pseudozufallszahlengenerator | Stochastik

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Spektraltest (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.