Testen von Algorithmen zur Erzeugung zufälliger Variablen

Welche Methoden werden zum Testen von Algorithmen zur Erzeugung von Zufallsvariablen verwendet?

Das Diehard Test Suite entspricht in etwa einem Goldenen Standard zum Testen von Zufallszahlengeneratoren. Es enthält eine Reihe von Tests, bei denen ein guter Zufallszahlengenerator ein Ergebnis liefern sollte, das gemäß einer bekannten Verteilung verteilt ist, mit der das Ergebnis unter Verwendung des getesteten Generators verglichen werden kann.

BEARBEITEN

Ich muss dies aktualisieren, da ich nicht genau recht hatte: Diehard wird möglicherweise noch häufig verwendet, ist aber nicht mehr gewartet und nicht mehr auf dem neuesten Stand der Technik. NIST hat seitdem eine Reihe verbesserter Tests entwickelt .

Nur um Honks Antwort ein wenig zu ergänzen, die Diehard Test Suite von George Marsaglia entwickelte ist der Standard für PRNG.

Es gibt eine schöne Diehard C-Bibliothek , mit der Sie auf diese Tests zugreifen können. Neben den Standard-Diehard-Tests stehen Funktionen für einige andere PRNG-Tests zur Verfügung, bei denen unter anderem die Bitreihenfolge überprüft wird. Es gibt auch eine Möglichkeit, die Geschwindigkeit des RNG zu testen und eigene Tests zu schreiben.

Es gibt eine R-Schnittstelle zur Dieharder-Bibliothek namens RDieHarder :

library(RDieHarder)
dhtest = dieharder(rng="randu", test=10, psamples=100, seed=12345)
print(dhtest)

Diehard Count the 1s Test (byte)

       data:  Created by RNG `randu' with seed=12345, 
              sample of size 100 p-value < 2.2e-16

Dies zeigt, dass der RANDU RNG-Generator den Minimum-Distance / 2dsphere-Test nicht besteht.

Für das Testen der von Zufallsgeneratoren erzeugten Zahlen sind die Diehard-Tests ein praktischer Ansatz. Aber diese Tests scheinen willkürlich und man kann sich fragen, ob mehr enthalten sein sollten oder ob es irgendeine Möglichkeit gibt, die Zufälligkeit wirklich zu überprüfen.

Der beste Kandidat für eine Definition einer Zufallsfolge scheint die Martin-Löf-Zufälligkeit zu sein . Die Hauptidee für diese Art von Zufälligkeit ist in Knuth, Abschnitt 3.5 , wunderschön entwickelt , sehr , besteht darin, die Gleichförmigkeit für alle Arten von Teilsequenzen der Folge von Zufallszahlen zu testen. So erhalten Sie alle Arten von Teilsequenzen stellte sich heraus, dass es sehr schwierig ist Teilsequenzen richtig zu definieren, selbst wenn man Begriffe der Berechenbarkeit verwendet.

Die Diehard-Tests sind nur einige der möglichen Untersequenzen, deren Misserfolg die Zufälligkeit von Martin Löf ausschließen würde.

Sie können nicht beweisen, weil es unmöglich ist; Sie können nur überprüfen, ob es keine peinlichen Autokorrelationen oder Verteilungsstörungen gibt, und Diehard ist in der Tat ein Standard dafür. Für die Statistik / Physik werden Kryptografen unter anderem auch prüfen, wie schwierig es ist, den Generator an die Daten anzupassen, um die zukünftigen Werte zu erhalten.

Kleine Korrektur an Colins Beitrag: Das CRAN-Paket RDieHarder ist eine Schnittstelle zu DieHarder , dem von Robert G. Brown (der mich freundlicherweise als Mitautor auf der Grundlage meiner RDieHarder-Wrapper auflistet) durchgeführten Umschreiben / Erweitern / Überarbeiten von Diehard .

Unter anderem enthält DieHarder die in Marks Beitrag erwähnte NIST-Testbatterie sowie einige neue. Dies ist eine fortlaufende Forschung und das schon eine Weile. Ich hielt einen Vortrag bei useR! 2007 über RDieHarder, den Sie hier bekommen können .

Es ist selten sinnvoll zu folgern, dass etwas abstrakt "zufällig" ist. Häufiger möchten Sie testen, ob es eine bestimmte Art von zufälliger Struktur hat. Beispielsweise möchten Sie möglicherweise testen, ob eine Einheitsverteilung vorliegt, wobei alle Werte in einem bestimmten Bereich gleich wahrscheinlich sind. Oder Sie möchten möglicherweise testen, ob etwas eine Normalverteilung usw. aufweist. Um zu testen, ob Daten eine bestimmte Verteilung aufweisen, können Sie einen Anpassungstest wie den Chi-Quadrat-Test oder den Kolmogorov-Smirnov-Test verwenden.

Das Testen eines Zufallszahlengenerators besteht aus zwei Teilen. Wenn Sie nur einen einheitlichen Generator testen möchten, ist so etwas wie die DIEHARD-Testsuite eine gute Idee.

Oft muss man aber eine Transformation eines einheitlichen Generators testen. Sie können beispielsweise einen einheitlichen Generator verwenden, um exponentiell oder normal verteilte Werte zu erstellen. Möglicherweise verfügen Sie über einen qualitativ hochwertigen, einheitlichen Generator - beispielsweise über eine vertrauenswürdige Implementierung eines bekannten Algorithmus wie Mersenne Twister -, aber Sie müssen testen, ob die transformierte Ausgabe die richtige Verteilung aufweist. In diesem Fall müssen Sie einen Fitnesstest wie Kolmogorov-Smirnov durchführen. Für den Anfang können Sie jedoch überprüfen, ob der Stichprobenmittelwert und die Varianz die von Ihnen erwarteten Werte aufweisen.

Die meisten Leute schreiben - und sollten - ihren eigenen einheitlichen Zufallszahlengenerator nicht von Grund auf neu. Es ist schwer, einen guten Generator zu schreiben, und man kann sich leicht vormachen, einen guten zu schreiben, wenn man es nicht getan hat. Zum Beispiel erzählt Donald Knuth in TAOCP Band 2 die Geschichte eines Zufallsgenerators, den er geschrieben hat und der sich als schrecklich herausgestellt hat. Es ist jedoch üblich, dass Benutzer ihren eigenen Code schreiben müssen, um zufällige Werte aus einer neuen Distribution zu generieren.

Das NIST veröffentlicht eine Liste statistischer Tests mit einer Referenzimplementierung in C.

Es gibt auch TestU01 von einigen klugen Leuten, einschließlich des angesehenen PRNG-Forschers Pierre L'Ecuyer. Wieder gibt es eine Referenzimplementierung in C.

Wie von anderen Kommentatoren ausgeführt, dienen diese zum Testen der Erzeugung von Pseudozufallsbits. Wenn Sie diese Bits in eine andere Zufallsvariable transformieren (z. B. Box-Muller-Transformation von Uniform zu Normal), benötigen Sie zusätzliche Tests, um die Richtigkeit des Transformationsalgorithmus zu bestätigen.