Scrambling und Korrelation in Sequenzen mit geringer Diskrepanz (Halton / Sobol)

14

Ich arbeite derzeit an einem Projekt, in dem ich Zufallswerte mithilfe von quasi-zufälligen Punktmengen mit geringer Diskrepanz generiere , z. B. Halton- und Sobol-Punktmengen. Dies sind im Wesentlichen d dimensionale Vektoren, die eine d dimensionale einheitliche (0,1) Variable imitieren , jedoch eine bessere Streuung aufweisen. Theoretisch sollen sie dazu beitragen, die Varianz meiner Schätzungen in einem anderen Teil des Projekts zu verringern.

Leider bin ich auf Probleme gestoßen, mit denen ich gearbeitet habe, und ein Großteil der Literatur über sie ist dicht. Ich hatte daher die Hoffnung, von jemandem, der Erfahrung mit ihnen hat, einen Einblick zu bekommen oder zumindest einen Weg zu finden, um empirisch zu bewerten, was vor sich geht:

Wenn Sie mit ihnen gearbeitet haben:

  • Was genau ist Scrambling? Und wie wirkt es sich auf den Strom der erzeugten Punkte aus? Gibt es insbesondere einen Effekt, wenn die Dimension der Punkte, die generiert werden, zunimmt?

  • Warum erhalte ich zwei verschiedene Punkteströme, wenn ich mit MatousekAffineOwen Scrambling zwei Sobol-Punkteströme generiere? Warum ist dies nicht der Fall, wenn ich mit Halton-Punkten das Reverse-Radix-Scrambling verwende? Gibt es andere Verschlüsselungsmethoden für diese Punktmengen - und wenn ja, gibt es eine MATLAB-Implementierung davon?

Wenn Sie nicht mit ihnen gearbeitet haben:

  • Angenommen, ich habe Folgen S 1 , S 2 , ... , S n von vermeintlich zufälligen Zahlen. Welche Art von Statistik sollte ich verwenden, um zu zeigen, dass sie nicht miteinander korrelieren? Und welche Zahl n würde ich benötigen, um zu beweisen, dass mein Ergebnis statistisch signifikant ist? Wie könnte ich dasselbe tun, wenn ich n Folgen S 1 , S 2 , ... , S n von d- dimensionalen Zufallsvektoren [ 0 , 1 ] hätte ?nS1,S2,…,SnnnS1,S2,…,Snd[0,1]

Anschlussfragen zu Kardinals Antwort

  1. Kann man theoretisch jede Verschlüsselungsmethode mit einer Sequenz mit geringer Diskrepanz kombinieren? In MATLAB kann ich Halton-Sequenzen nur mit einem umgekehrten Radix-Scrambling versehen. Ich frage mich, ob dies nur ein Implementierungs- oder ein Kompatibilitätsproblem ist.

  2. Ich suche nach einer Möglichkeit, mit der ich zwei (t, m, s) Netze erzeugen kann, die nicht miteinander korreliert sind. Erlaubt mir MatouseAffineOwen dies? Wie wäre es, wenn ich einen deterministischen Scrambling-Algorithmus verwenden würde und einfach jeden k-ten Wert wählen würde, bei dem k eine Primzahl ist?

hypothesis-testing monte-carlo random-generation randomness Berk U.
quelle
Was meinen Sie damit, dass zwei Netze nicht korreliert sind? Was bedeutet dies insbesondere, wenn Sie sagen "Wir verwenden einen deterministischen Verschlüsselungsalgorithmus"? Viele Verschlüsselungsalgorithmen können auf beliebige ( t , m , s ) Netze angewendet werden . Ich weiß ehrlich gesagt nicht, ob alle Programme funktionieren. Ich könnte mir vorstellen, dass die Antwort "nein" lautet. (Das heißt, man könnte ein Scrambling konstruieren, das so spezialisiert ist, dass es die Closure-Eigenschaft für eine bestimmte Sequenz beibehält , aber nicht im Allgemeinen. Ich kenne das nicht von der Hand.)(t,m,s)(t,m,s)
Kardinal
@ Kardinal Sorry, das war unklar, also lass mich versuchen, es neu zu phasen. Angenommen, ich habe zwei Netze P und Q , mit denen ich zwei Folgen von 100 Punkten generiere, { p i } 100 1 und { q i } 100 1 . Wenn ich einen Zufallsverwürfelungsalgorithmus verwende, dann { p i } 100 1 und { q i } 100 1(t,m,s)PQ{pi}1100{qi}1100{pi}1100{qi}1100sollte nicht korreliert sein, oder? Dies ist offensichtlich nicht wahr, wenn ich einen deterministischen Verschlüsselungsalgorithmus verwendet hätte. Aber was , wenn 200 Punkte erzeugt und nur gehalten , selbst Einträge von und ungeradeen Einträgen aus { q i } 200 1 . Würden diese miteinander korrelieren? Und würden sie immer noch schön "ausgebreitet" sein? {pi}1200{qi}1200
Berk U.
ja, wenn Sie zwei separate Netze unabhängig voneinander zufällig verschlüsseln , sind die resultierenden Sätze unabhängig. Was einen deterministischen Verwürfelungsalgorithmus betrifft, so kann es ohne den Begriff der Zufälligkeit keinen richtigen Begriff der Korrelation geben. Ich musste darüber nachdenken, gerade und ungerade Einträge zu machen. Der Standardansatz wäre, ein paar Punkte für den ersten zu sammeln, dann ein paar weitere Punkte zu generieren und wegzuwerfen und dann den zweiten Satz Punkte zu sammeln. Dies hängt mit der Verwendung von "eingebrannten" Sätzen von QMC-Punkten zusammen. (t,m,s)
Kardinal

Antworten:

10

Das Verwürfeln ist normalerweise eine Operation, die auf ein digitales Netz angewendet wird, das eine Basis b verwendet . Sobol-Netze verwenden zum Beispiel b = 2 , während Faure-Netze eine Primzahl für b verwenden .(t,m,s)bb=2b

Der Zweck des Verwürfelns ist (hoffentlich) eine noch gleichmäßigere Verteilung, insbesondere wenn Sie nur eine kleine Anzahl von Punkten verwenden können. Ein gutes Beispiel, um zu sehen, warum dies funktioniert, ist, die Halton-Sequenz in und zwei "größere" Primzahlen wie 29 und 31 zu wählen. Das Quadrat wird mit der Standard-Halton-Sequenz sehr langsam ausgefüllt. Beim Scrambling wird es jedoch viel schneller und gleichmäßiger ausgefüllt. Hier ist ein Plot für die ersten paar hundert Punkte unter Verwendung eines deterministischen Scrambling-Ansatzes.d=2

enter image description here

Die grundlegendsten Formen des Verwürfelns lassen im Wesentlichen die stelligen Basiserweiterungen der ursprünglichen n Punkte untereinander durch. Für weitere Details hier eine klare Darstellung .bn

(t,m,s)(t,m,s)(t,m,s)

In Bezug auf die Arten des Verwürfelns ist das Verwürfeln mit umgekehrter Basis ein deterministisches Verwürfeln. Der Matousek-Scrambling-Algorithmus ist ein zufälliges Scramble, das ebenfalls so durchgeführt wird, dass die Verschlusseigenschaft erhalten bleibt. Wenn Sie den Zufallsstartwert festlegen, bevor Sie die Verschlüsselungsfunktion aufrufen, sollten Sie immer das gleiche Netz zurückerhalten.

Das MinT-Projekt könnte Sie auch interessieren .

Kardinal
quelle
Vielen Dank dafür. Ich hatte einige Nachfragen, wenn es Ihnen nichts ausmacht. Da ich sie im Kommentarfeld nicht klar auflisten kann, habe ich sie in den Beitrag aufgenommen.
Berk U.