Ich verwende seit einiger Zeit Sequenzen mit geringer Diskrepanz für Gleichverteilungen, da ich ihre Eigenschaften als nützlich empfunden habe (hauptsächlich in Computergrafiken wegen ihres zufälligen Erscheinungsbilds und ihrer Fähigkeit, [0,1] inkrementell dicht zu bedecken).
Zum Beispiel zufällige Werte oben, Halton-Sequenzwerte unten:
Ich habe überlegt, sie für eine Finanzanalyseplanung zu verwenden, aber ich brauche andere Verteilungen als nur einheitliche. Ich habe zunächst versucht, aus meinen Gleichverteilungen über den Marsaglia-Polaralgorithmus eine Normalverteilung zu generieren, aber die Ergebnisse scheinen nicht so gut zu sein wie bei der Gleichverteilung.
Ein weiteres Beispiel, wieder zufällig oben, Halton unten:
Meine Frage ist: Was ist die beste Methode, um eine Normalverteilung mit den Eigenschaften zu erhalten, die ich aus einer einheitlichen Sequenz mit geringer Diskrepanz erhalte - Abdeckung, inkrementelles Ausfüllen, Nichtkorrelation über mehrere Dimensionen hinweg? Bin ich auf dem richtigen Weg oder sollte ich einen ganz anderen Ansatz verfolgen?
(Python-Code für einheitliche und normale Verteilungen, den ich oben verwende: Gist 2566569 )
quelle
Antworten:
scipyquelle
Ich bin kürzlich auf dieses Problem gestoßen. Naiv dachte ich, dass jede Transformation von Uniform funktionieren würde, also steckte ich eine 1D Sobol (und Halton) Sequenz ein, als ob die Sequenz ein Zufallszahlengenerator in eine
std::normal_distribution<>Variable wäre. Zu meiner Überraschung hat es nicht funktioniert, es hat offensichtlich eine nicht normale Verteilung erzeugt.Ok, dann habe ich die Funktion Numerical Recipes Third Edition Chapter 7.3.9
Normal_devverwendet, um normale Zahlen aus den Sobol- oder Halton-Sequenzen nach der Methode "Ratio-of-Uniforms" zu generieren, und sie ist auf die gleiche Weise fehlgeschlagen. Dann denke ich, ok, wenn Sie sich den Code ansehen, sind zwei einheitliche Zufallszahlen erforderlich, um zwei normalverteilte Zufallszahlen zu generieren. Vielleicht funktioniert es, wenn ich eine Sobol (oder Halton) 2D-Sequenz verwendet habe. Nun, es ist wieder gescheitert.Ich erinnerte mich an die "Box-Muller-Methode" (in den Kommentaren erwähnt) und da sie eine geometrischere Interpretation hat, dachte ich, dass sie funktionieren könnte. Nun, es hat funktioniert! Ich war sehr aufgeregt, einen anderen Test zu machen, die Verteilung sieht normal aus.
Das Problem, das ich sah, war, dass die Verteilung nicht besser als zufällig war, was die Füllung betrifft. Ich war ein bisschen enttäuscht, aber bereit, das Ergebnis zu veröffentlichen.
Dann habe ich eine tiefere Suche durchgeführt (jetzt, da ich wusste, wonach ich suchen sollte), und es stellte sich heraus, dass es bereits ein Papier zu diesem Thema gibt: http://www.sciencedirect.com/science/article/pii/S0895717710005935
In diesem Artikel wird es tatsächlich behauptet
Die allgemeine Schlussfolgerung lautet also:
1) Sie können den Box-Muller für 2D-Sequenzen mit geringer Diskrepanz verwenden, um normalverteilte Sequenzen zu erhalten. Meine wenigen Experimente scheinen jedoch zu zeigen, dass die geringe Diskrepanz / der geringe Abstand, z. B. die Fülleigenschaften, in der normal transformierten Sequenz verloren gehen.
2) Sie können die inverse Methode verwenden, wobei vermutlich die geringen Diskrepanz- / Raumfüllungseigenschaften erhalten bleiben.
3) Verhältnis der Uniformen kann nicht verwendet werden.
EDIT : Diese https://mathoverflow.net/a/144234 verweist auf die gleichen Schlussfolgerungen.
Ich habe eine Illustration gemacht (die erste Abbildung (Verhältnis der Uniformen bei Sobol) zeigt, dass die erhaltene Verteilung nicht normal ist, aber die Ohters (Box-Muller und zufällig zum Vergleich) sind):
EDIT2:
Der Hauptpunkt ist, dass selbst wenn Sie eine Methode finden, die die "Verteilung" einer Sequenz mit geringer Diskrepanz transformieren kann, es nicht offensichtlich ist, dass Sie die guten Fülleigenschaften beibehalten. Sie sind also nicht besser als mit einer wirklich zufälligen (Standard-) Normalverteilung. Ich habe noch keine Methode gefunden, die eine geringe Diskrepanz aufweist und sich dennoch gut mit einer ungleichmäßigen Verteilung füllt. Ich wette, eine solche Methode ist nicht offensichtlich und vielleicht ein offenes Problem.
quelle
Es gibt zwei gute Methoden. Zunächst kann, wie oben erwähnt, eine genaue Annäherung an die Umkehrung der Gaußschen Verteilung verwendet werden. Dann kann man jede Sequenz mit geringer Diskrepanz in eine Gaußsche Sequenz umwandeln.
Die zweite Methode ist der Box-Muller. Diese Methode erfordert zwei Eingangsnummern (R und A) und erzeugt zwei Ausgänge. Eine zweidimensionale Sequenz mit geringer Diskrepanz wird benötigt. Man nimmt (zum Beispiel in der Halton-Sequenz), Primzahlenpaare werden verwendet, eines für die Radialkomponente (R) und eines für die Winkelkomponente (A). Man erhält Sqrt (-2 * Log (R)) für die radiale Komponente und Sin (2 * Pi * A) und Cos (2 * Pi * A) für die Winkelkomponenten. Das Multiplizieren des Radials mit den beiden Winkelkomponenten (getrennt) ergibt zwei Gaußsche. Der Wirkungsgrad ist der gleiche wie oben; zwei quasi zufällige Eingänge und zwei Gaußsche Ausgänge.
Abhängig von der Dimensionalität des Problems kann jede mehrdimensionale Sequenz mit geringer Diskrepanz verwendet werden.
quelle
Die nativste Methode wäre zwar die Verwendung der inversen CDF zur Transformation in eine normale Gaußsche, aber es gibt auch Probleme damit. Wenn Sie z. B. einen LDS-Punktsatz haben, der durch Rang-1-Gitter erstellt wurde, ist der Startpunkt immer (0,0). Um ihn zu transformieren, benötigen Sie eine kleine Verschiebung, am besten die gleiche Lücke wie für den Ecke (1,1).
quelle