Qualität linearer Kongruenzgeneratoren für Zufallszahlen

Ich mache einige Simulationen der Langevin-Gleichung für verschiedene äußere Kräfte. Da mir gesagt wird, dass Cs rand()von zu stdlib.hVerzerrungen in meinen Ergebnissen führen können, verwende ich einen Mersenne Twister.

Trotzdem möchte ich genau wissen (und sehen), welche Art von Fehlern ein linearer Kongruenzgenerator in meine Simulation einbringen kann. Dies sind Dinge, die ich ausprobiert habe:

• Generieren von 3D-Tupeln von Zufällen, um zu versuchen, Hyperebenen zu sehen. Ich kann nichts sehen.
• Ausführen der FFT eines großen Vektors von Zufallszahlen. Es ist fast das gleiche für den Mersenne Twister und rand().
• Überprüfung des Equipartition-Prinzips für ein Teilchen in Brownscher Bewegung. Beide Integratoren stimmen im erwarteten Wert von mit der gleichen Anzahl signifikanter Stellen .$\langle \text{KE}\rangle=\frac{1}{2}k_BT$
• Zu sehen, wie gut sie in einer Anzahl von Behältern sind, die keine Potenz zwei ist. Beide liefern die gleichen qualitativen Ergebnisse, keiner ist besser.
• Schauen Sie sich die Brownschen Pfade an, um klare Abweichungen von . Wieder kein Glück.$\langle x\rangle = 0$
• Punkteverteilung im Kreis. Gefüllt und nur im Umkreis. Zwischen allen und zwischen den nächsten Nachbarn (Shors Antwort unten in den Kommentaren). In dieser Liste verfügbar , führen Sie sie einfach mit Julia 0.5.0 aus, nachdem Sie die erforderlichen Bibliotheken installiert haben (Anweisungen finden Sie in der Liste).

Ich möchte betonen, dass ich nach einer eingeführten Verzerrung im Kontext physikalischer Simulationen suche. Ich habe zum Beispiel gesehen, wie rand()kläglich die härtesten Tests scheitern, während der Mersenne Twister es nicht tut, aber im Moment bedeutet das nicht zu viel für mich.

Haben Sie physikalische, konkrete Beispiele, wie ein schlechter Zufallszahlengenerator eine Montecarlo-Simulation zerstört?

Hinweis: Ich habe gesehen, wie RANDUschrecklich PRNG sein kann. Ich interessiere mich für nicht offensichtliche Beispiele von Generatoren, die unschuldig aussehen, aber letztendlich Voreingenommenheit hervorrufen.

Eine interessante Literaturstelle, die ein Versagen einer Monte-Carlo-Simulation eines physikalischen Systems aufgrund von unzureichendem RNG beschreibt (obwohl sie kein LCG verwendeten), ist:

A. Ferrenberg und DP Landau. Monte-Carlo-Simulationen: Versteckte Fehler von "guten" Zufallszahlengeneratoren. Physical Review Letters 63 (23): 3382-3384, 1992.

Die von Ferrenberg und Landua untersuchten Ising-Modelle sind gute Tests für RNGs, da Sie sie mit einer exakten Lösung (für das 2-D-Problem) vergleichen und Fehler in den Ziffern finden können. Diese Modelle sollten die Fehler in einem altmodischen 32-Bit-PMMLCG ohne allzu große Schwierigkeiten anzeigen.

Eine weitere interessante Referenz ist:

H. Bauke und Stephan Mertens. Pseudozufällige Münzen zeigen mehr Köpfe als Schwänze. arXiv: cond-mat / 0307138 [cond-mat.stat-mech]

Bauke und Mertens sprechen sich nachdrücklich gegen Zufallszahlengeneratoren mit binärer linearer Rückkopplung aus. Bauke und Mertens haben einige andere Arbeiten dazu.

Es kann schwierig sein, die Marsaglia-Ebenen in einem 3D-Streudiagramm zu finden. Sie können versuchen, den Plot zu drehen, um eine bessere Ansicht zu erhalten, und manchmal werden sie einfach bei Ihnen herausspringen. Sie können auch 3D-Tests der statistischen Einheitlichkeit durchführen. Bei älteren 32-Bit-LCGs schlägt dies bei einer relativ geringen Anzahl von Behältern fehl. Zum Beispiel ist ein Homogenitätstest mit einem 20x20x20-Gitter von Behältern in drei Dimensionen ausreichend, um eine mangelnde Homogenität für das weit verbreitete (und früher gut angesehene) PMMLCG mit m = 2 ^ 31-1, a = 7 ^ 5 festzustellen.

Es ist möglich, die PRNG-Testsuite TestU01 zu verwenden , um herauszufinden, welcher dieser Tests randfehlschlägt. ( Eine Übersicht über die Testsuite finden Sie unter TestU01: AC-Bibliothek für das empirische Testen von Zufallszahlengeneratoren .) Das ist einfacher, als eigene Monte-Carlo-Simulationen zu entwickeln. In gewisser Weise ist es auch eine Frage der Software-Kompositionsfähigkeit (und der Software-Korrektheit): Wenn ein PRNG für kleine, einfache Tests in Ordnung zu sein scheint, woher wissen Sie, dass sein pathologisches Verhalten nicht durch ein größeres Programm ausgelöst wird?

Hier ist der Code:

#include "TestU01.h"

int main() {
  // Same as rand() on my machine
  unif01_Gen* gen = ulcg_CreateLCG(2147483647, 16807, 0, 12345);

  bbattery_SmallCrush(gen);
  bbattery_Crush(gen);

  return 0;
}

Für die SmallCrush- Suite gibt es 3 von 15 fehlgeschlagene Tests ( ausführliche Beschreibungen und alle Referenzen finden Sie unter guidelongtestu01.pdf in TestU01; dies sind 15 Statistiken aus 10 Tests).

• $n$ $t$$d^t$$d^t$$I_1,\ldots$$\{I_{j+1}-I_j\}$

• $n$ $t$$[0,1)^t$$d^t$

• $n$$t$$[0,1)$$X$$n$$\mathbb{P}(X<x) = x^t$$n=2\times 10^6$$t=6$$\chi^2$$<10^{-300}$

Angenommen, dies sind alles "typische" Monte-Carlo-Simulationen (obwohl sie möglicherweise nicht den von Ihnen in Betracht gezogenen Problemen entsprechen), ist die Schlussfolgerung, dass randeine unbekannte Untergruppe von ihnen fehlschlägt. Ich weiß jedoch nicht, warum es sich speziell um diese Untergruppe handelt, daher kann ich nicht sagen, ob es bei Ihrem eigenen Problem funktioniert oder nicht.

Besonders verdächtig wirkt MaxOft , wenn man bedenkt , wie einfach die Beschreibung ist.

Unter den Tests in der Crush- Suite fallen rand51 von 140 aus (140 Statistiken in 96 Tests). Einige der fehlgeschlagenen Tests (wie Fourier3 ) werden mit Bit-Strings durchgeführt, daher ist es möglich, dass sie für Sie nicht relevant sind. Ein anderer merkwürdiger Test, der fehlschlägt, ist GCD , der die Verteilung der GCD von zwei zufälligen ganzen Zahlen testet. (Auch hier weiß ich nicht, warum dieser Test fehlschlägt oder ob Ihre Simulation darunter leiden wird.)

PS : Noch eine andere Sache zu beachten ist , dass rand()ist tatsächlich langsamer als einige PRNGs , die erfolgreich alle den Pass SmallCrush , Crush , BigCrush Tests, wie MRG32k3a (siehe L'Ecuyer & Simard Papier oben).