Mieszanie i korelacja w sekwencjach niskiej rozbieżności (Halton / Sobol)

14

Obecnie pracuję nad projektem, w którym generuję wartości losowe przy użyciu zestawów punktów o niskiej rozbieżności / quasi-losowych , takich jak zestawy punktów Halton i Sobol. Są to zasadniczo wektory d wymiarowe, które naśladują zmienne d wymiarowe jednolite (0,1), ale mają lepszy rozkład. Teoretycznie mają one pomóc w zmniejszeniu wariancji moich szacunków w innej części projektu.

Niestety, miałem problemy z pracą z nimi i znaczna część literatury na ich temat jest gęsta. Miałem więc nadzieję uzyskać wgląd od kogoś, kto ma z nimi doświadczenie, lub przynajmniej znaleźć sposób na empiryczną ocenę tego, co się dzieje:

Jeśli pracowałeś z nimi:

  • Czym dokładnie jest szyfrowanie? A jaki to ma wpływ na strumień generowanych punktów? W szczególności, czy występuje efekt, gdy wzrasta wymiar generowanych punktów?

  • Dlaczego tak jest, że jeśli wygeneruję dwa strumienie punktów Sobola za pomocą mieszania MatousekAffineOwen, otrzymam dwa różne strumienie punktów. Dlaczego tak nie jest, gdy używam szyfrowania wstecznego z punktami Halton? Czy istnieją inne metody szyfrowania dla tych zestawów punktów - a jeśli tak, to czy istnieje ich implementacja MATLAB?

Jeśli nie pracowałeś z nimi:

  • Powiedzmy, że mam sekwencji S 1 , S 2 , , S n liczb przypuszczalnie losowych, jakiego rodzaju statystyki powinienem użyć, aby pokazać, że nie są ze sobą skorelowane? A jakiej liczby n potrzebowałbym, aby udowodnić, że mój wynik jest statystycznie istotny? Ponadto, jak można zrobić to samo w przypadku miałem n sekwencji S 1 , S, 2 , ... , S n z d -wymiarową losowych [ 0 , 1 ] wektorów?nS1,S2,,SnnnS1,S2,,Snd[0,1]

Dalsze pytania dotyczące odpowiedzi kardynała

  1. Teoretycznie, czy możemy sparować dowolną metodę szyfrowania z dowolną sekwencją o niskiej rozbieżności? MATLAB pozwala mi jedynie na zastosowanie szyfrowania wstecznego na sekwencjach Haltona i zastanawiam się, czy jest to po prostu kwestia implementacji, czy kwestia kompatybilności.

  2. Szukam sposobu, który pozwoli mi wygenerować dwie sieci (t, m, s), które nie są ze sobą powiązane. Czy MatouseAffineOwen pozwoli mi to zrobić? Co powiesz na to, że użyłem deterministycznego algorytmu szyfrującego i po prostu zdecydowałem się wybrać każdą wartość „kth”, gdzie k było liczbą pierwszą?

Berk U.
źródło
co masz na myśli mówiąc, że dwie sieci są nieskorelowane? W szczególności, co to znaczy, kiedy mówimy „determinując algorytm szyfrujący”? Wiele algorytmów szyfrujących można zastosować do dowolnych sieci ( t , m , s ) ; Szczerze mówiąc, nie wiem, czy wszystkie programy się sprawdzają. Wyobrażam sobie, że odpowiedź może brzmieć „nie”. (To znaczy, można zbudować szyfrowanie, które było na tyle wyspecjalizowane, że zachowało właściwość zamykania dla określonej sekwencji, ale ogólnie nie. Nie wiem o tym z ręki.)(t,m,s)(t,m,s)
kardynał
@ kardynał Przepraszam, że to było niejasne, więc pozwól mi spróbować go zmienić. Powiedzmy, że mam dwie sieci P i Q , których używam do generowania dwóch sekwencji po 100 punktów, { p i } 100 1 i { q i } 100 1 . Jeśli użyję algorytmu losowego szyfrowania, wtedy { p i } 100 1 i { q i } 100 1(t,m,s)PQ{pi}1100{qi}1100{pi}1100{qi}1100powinien być nieskorelowany, prawda? Oczywiście nie jest to prawdą, jeśli użyłem deterministycznego algorytmu szyfrującego. Ale co, jeśli wygeneruje 200 punktów i zachowa tylko parzyste wpisy i nieparzyste wpisy z { q i } 200 1 . Czy byłyby one skorelowane? I czy nadal będą ładnie „rozłożone”? {pi}1200{qi}1200
Berk U.
tak, jeśli losowo zaszyfrujesz dwie oddzielne sieci niezależnie od siebie, wówczas zestawy wynikowe będą niezależne. Jeśli chodzi o deterministyczny algorytm szyfrowania, bez pojęcia losowości, tak naprawdę nie może istnieć właściwe pojęcie korelacji. Musiałbym pomyśleć o przyjmowaniu parzystych i dziwnych wpisów. Standardowym podejściem byłoby zdobycie kilku punktów za pierwszy, a następnie wygenerowanie i wyrzucenie kilku punktów, a następnie zebranie drugiego zestawu punktów. Jest to związane z użyciem „wypalonych” zestawów punktów QMC. (t,m,s)
kardynał

Odpowiedzi:

10

Szyfrowanie jest zwykle operacją stosowaną do sieci cyfrowej która wykorzystuje pewną bazę b . Sieci Sobol używają na przykład b = 2 , podczas gdy sieci Faure używają liczby pierwszej dla b(t,m,s)bb=2b .

d=2

enter image description here

bn

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

Jeśli chodzi o typy mieszania, mieszanie z odwrotnym radikiem jest mieszaniem deterministycznym . Algorytm szyfrowania Matousek jest losowym szyfrowaniem, wykonywanym ponownie w celu zachowania właściwości zamknięcia. Jeśli ustawisz losowe ziarno przed wywołaniem funkcji szyfrowania, zawsze powinieneś odzyskać tę samą sieć.

Możesz być także zainteresowany projektem MinT .

kardynał
źródło
Dziękuję bardzo za to. Miałem kilka dodatkowych pytań, jeśli nie masz nic przeciwko. Ponieważ pole komentarza nie pozwala mi wyraźnie ich wymienić, umieściłem je w poście.
Berk U.