Spektraltest

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

Der Spektraltest ist eine theoretische Methode, mit der Zufallszahlen auf ihre Unabhängigkeit überprüft werden können. Dabei 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.

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

Bei speziellen Generatoren (LKG) gibt es sogar Algorithmen, die das exakte Ergebnis mit relativ geringem Rechenaufwand liefern.

(Dieser Artikel entstand aufgrund einer Diskussion der Zwölferregel. Siehe dort)

[Bearbeiten] Details

Zufallszahlen müssen irgendwie gewonnen werden. Wenn man keinen physikalischen Mechanismus (Radioaktivität, echter Würfel) an den Rechner anschließt, geschieht das in der Regel mit Pseudozufallszahlengeneratoren.

Stand der Technik sind dabei die sog. LKG (Linearer Kongruenzgenerator) mit der Formel $x = (a \cdot x + c) \, \textrm{ mod } \, m$ und festen Konstanten a, c, m).

Die Unabhängigkeit der generierten Zufallszahlen wird mit dem erwähnten Spektraltest getestet. (Ungetestete Generatoren sollten sowieso nie verwendet werden.)

Der Spektraltest liefert als Ergebnis, wieviele aufeinanderfolgene Zahlen noch als unabhängig gelten können und wie gut sie unabhängig sind. Das geschieht mit $\nu_2, \nu_3, \nu_4, \nu_5 \ldots$ , die für jeweils 2, 3, 4, 5, ... aufeinanderfolgende Zufallszahlen deren Qualität angeben.

Der Kehrwert $1 / ν i$ ist dabei der kleinste Abstand der (i-1)-dimensionalen Hypergitterebenen im i-dimensionalen Raum von aufeinanderfolgenden i-tupeln der generierten Zahlen.

Je größer $ν i$ , also je kleiner $1 / ν i$ ist, umso besser verteilen sich die Vektoren in ihrem Wertebereich, umso dichter lieger sie und umso mehr Dezimalstellen dürfen verwendet werden.

[Bearbeiten] Beispiele

Generator mit $m = 10000000000 = 10^{10}; \, a = 3141592621; \, c = 1; \, x_0 = 0$ . Der Spektraltest liefert $\nu_2 = 67654; \, \nu_3 = 1017; \, \nu_4 = 249; \, \nu_5 = 42; \, \nu_6 = 23; \, \nu_7 = 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 / ν 2 = 1 / 67654 = 0.0000148 < 10 - 4 = 4$ Dezimalstellen angeben. Wenn man drei pro Rechnung benötigt sind das $1 / ν 3 = 1 / 1017 = 0.000938 < 10 - 3 = 3$ Dezimalstellen. Bei vier pro Rechnung ergibt sich $1 / ν 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 übrigens ein brauchbarer. Es gibt zwar bessere, aber leider noch mehr sehr viel schlechtere, wie das nächste Beispiel zeigt.

Das Horrorbeispiel der Statistiker ist der leider oft verwendete Generator randu mit $m = 2147483648 = 2^{31}; \, a = 65539 = 2^{16}+3; \, c = 0; \, x_0 = 0$ und dem Spektraltestergebnis $\nu_2 = 23171; \, \nu_3 = \sqrt{118} = 10; \, \nu_4 = \nu_5 = \nu_6 = \nu_7 = \nu_8 = \nu_9 = \sqrt{116} = 10$ . Alle i-tupel mit i > 2 haben maximal 1 Dezimalstelle Genauigkeit!