Fałszywe jednolite liczby losowe: bardziej równomiernie rozłożone niż prawdziwe jednolite dane

Szukam sposobu generowania liczb losowych, które wydają się być jednolicie rozmieszczone - a każdy test wykaże, że są one jednolite - z tym wyjątkiem, że są one bardziej równomiernie rozłożone niż prawdziwe jednolite dane .

Problem, jaki mam z „prawdziwymi” losowymi mundurami, polega na tym, że czasami się grupują. Efekt ten jest silniejszy przy małej wielkości próbki. Z grubsza powiedziane: kiedy narysuję dwa losowe Mundury w U [0; 1], szanse wynoszą około 10%, że są w zakresie 0,1, a 1%, że są w zakresie 0,01.

Więc szukam dobrego sposobu na generowanie liczb losowych, które są bardziej równomiernie rozłożone niż jednolite losowe .

Przykład użycia: powiedzmy, że gram w grę komputerową i chcę losowo umieszczać skarb na mapie (nie dbając o nic innego). Nie chcę, aby skarb znajdował się w jednym miejscu, powinien znajdować się na całej mapie. W przypadku losowych mundurów, jeśli umieszczę, powiedzmy, 10 obiektów, szanse nie są tak małe, że 5 lub tak naprawdę są blisko siebie. To może dać jednemu graczowi przewagę nad drugim. Pomyśl o trałowcu, szanse (choć niskie, jeśli jest wystarczająco dużo min) są takie, że masz szczęście i wygrywasz jednym kliknięciem.

Bardzo naiwnym podejściem do mojego problemu jest podzielenie danych na siatkę. Dopóki liczba jest wystarczająco duża (i zawiera czynniki), można w ten sposób wymusić dodatkową jednolitość. Zamiast więc rysować 12 zmiennych losowych z U [0; 1], mogę narysować 6 z U [0; .5] i 6 z U [0,5; 1] lub 4 z U [0; 1/3] + 4 od U [1/3; 2/3] + 4 od U [2/3; 1].

Czy istnieje lepszy sposób, aby wprowadzić tę dodatkową równość do munduru? Prawdopodobnie działa tylko dla losowych partii (podczas losowania pojedynczego losu, oczywiście muszę wziąć pod uwagę cały zakres). W szczególności mogę później przetasować nagrania (więc nie są to pierwsze cztery z pierwszego trzeciego).

Co powiesz na robienie tego stopniowo? Więc pierwsza jest na U [0; 1], a następnie dwie z każdej połowy, jedna z każdej trzeciej, jedna z każdej czwartej? Czy zostało to zbadane i jak dobre jest? Być może będę musiał ostrożnie używać różnych generatorów dla xiy, aby nie skorelować ich (pierwszy xy zawsze będzie w dolnej połowie, drugi w lewej połowie i dolnej trzeciej, trzeci w środkowej trzeciej i górnej trzeciej. .. więc potrzebna jest co najmniej losowa permutacja bin. W dłuższej perspektywie będzie ona zbyt wyrównana, tak myślę.

Jako węzeł boczny, czy istnieje dobrze znany test, czy niektóre rozkłady są zbyt równomiernie rozłożone, aby były naprawdę jednolite? Testowanie „prawdziwego munduru” vs. „ktoś pomieszał dane i rozłożył elementy bardziej równomiernie”. Jeśli dobrze pamiętam, statystyki Hopkinsa mogą to zmierzyć, ale czy można to również wykorzystać do testowania? Również nieco odwrotny test KS: jeśli największe odchylenie jest poniżej określonego oczekiwanego progu, dane są zbyt równomiernie rozłożone?

Tak , istnieje wiele sposobów tworzenia sekwencji liczb, które są bardziej równomiernie rozłożone niż losowe mundury. W rzeczywistości istnieje całe pole poświęcone temu pytaniu; jest to kręgosłup quasi-Monte Carlo (QMC). Poniżej znajduje się krótka prezentacja absolutnych podstaw.

Pomiar jednorodności

Można to zrobić na wiele sposobów, ale najczęstszy sposób ma silny, intuicyjny, geometryczny smak. Załóżmy, że zajmujemy się generowaniem punktów x 1 , x 2 , … , x n w [ 0 , 1 ] d dla pewnej dodatniej liczby całkowitej d . Zdefiniuj gdzie jest prostokątem w takim, że$n$$x_1,x_2,\ldots,x_n$$[0,1]^d$$d$R [ a 1 , b 1 ] × ⋯ × [ a d , b d

$$\newcommand{\I}{\mathbf 1} D_n := \sup_{R \in \mathcal R}\,\left|\frac{1}{n}\sum_{i=1}^n \I_{(x_i \in R)} - \mathrm{vol}(R)\right| \>,$$ $R$$[a_1, b_1] \times \cdots \times [a_d, b_d]$ 0 ≤ a i ≤ b i ≤ 1 R R R v o l ( R ) = ∏ i ( b i - I$[0,1]^d$$0 \leq a_i \leq b_i \leq 1$ a jest zbiorem wszystkich takich prostokątów. Pierwszy element w module to „obserwowana” proporcja punktów wewnątrz a drugi to objętość , .$\mathcal R$$R$$R$$\mathrm{vol}(R) = \prod_i (b_i - a_i)$

Wielkość jest często nazywana rozbieżnością lub skrajną rozbieżnością zbioru punktów . Intuicyjnie znajdujemy „najgorszy” prostokąt którym proporcja punktów najbardziej odbiega od tego, czego moglibyśmy oczekiwać przy idealnej jednolitości. ( x i ) $D_n$$(x_i)$$R$

Jest to niewygodne w praktyce i trudne do obliczenia. W przeważającej części ludzie wolą pracować z rozbieżnością między , Jedyną różnicą jest zbiór nad którym przejęte jest supremum. Jest to zestaw zakotwiczonych prostokątów (na początku), tj. Gdzie .A a 1 = a 2 = ⋯ = a d =

$$D_n^\star = \sup_{R \in \mathcal A} \,\left|\frac{1}{n}\sum_{i=1}^n \I_{(x_i \in R)} - \mathrm{vol}(R)\right| \>.$$ $\mathcal A$$a_1 = a_2 = \cdots = a_d = 0$

Lemat : dla wszystkich , . Dowód . Lewa ręka związany jest oczywiste ponieważ . Prawa granica jest następująca, ponieważ każdy może być skomponowany przez połączenia, przecięcia i uzupełnienia nie więcej niż zakotwiczonych prostokątów (tj. ). n d A ⊂ R R ∈ R 2 d $D_n^\star \leq D_n \leq 2^d D_n^\star$$n$$d$
$\mathcal A \subset \mathcal R$$R \in \mathcal R$$2^d$$\mathcal A$

Widzimy zatem, że i są równoważne w tym sensie, że jeśli jedno jest małe, gdy rośnie, drugie też będzie. Oto (kreskówkowy) obraz przedstawiający kandydujące prostokąty dla każdej rozbieżności.D ⋆ n$D_n$$D_n^\star$$n$

Przykłady „dobrych” sekwencji

Sekwencje o weryfikowalnie niskiej rozbieżności między są często nazywane, co nie jest zaskakujące, sekwencjami o niskiej rozbieżności .$D_n^\star$

van der Corput . To chyba najprostszy przykład. Dla sekwencje van der Corputa są tworzone przez rozszerzenie liczby całkowitej binarnie, a następnie „odzwierciedlenie cyfr” wokół kropki dziesiętnej. Bardziej formalnie, robi się to za pomocą radykalnej funkcji odwrotnej w bazie , gdzie i są cyframi w rozszerzeniu podstawy . Ta funkcja stanowi również podstawę wielu innych sekwencji. Na przykład w systemie binarnym to i tak daleji b ϕ b ( i ) = ∞ ∑ k = 0 a k b - k - $d=1$$i$$b$i = ∑ ∞ k = 0 a k b k a k b i 41 101001 a 0 =

$$\newcommand{\rinv}{\phi} \rinv_b(i) = \sum_{k=0}^\infty a_k b^{-k-1} \>,$$ $i = \sum_{k=0}^\infty a_k b^k$$a_k$$b$$i$$41$$101001$$a_0 = 1$ , , , , i . Dlatego 41. punkt w sekwencji van der Corputa to .a 2 = 0 a 3 = 1 a 4 = 0 a 5 = 1 x 41 = ϕ 2 ( 41 ) = $a_1 = 0$$a_2 = 0$$a_3 = 1$$a_4 = 0$$a_5 = 1$$x_{41} = \rinv_2(41) = 0.100101\,\text{(base 2)} = 37/64$

Zauważ, że ponieważ najmniej znaczący bit oscyluje między a , punkty dla nieparzystego są w , podczas gdy punkty dla parzystego są w .$i$1 x I I [ 1 / 2 , 1 ) x I I ( 0 , 1 / 2 $0$$1$$x_i$$i$$[1/2,1)$$x_i$$i$$(0,1/2)$

Sekwencje Haltona . Wśród najbardziej popularnych klasycznych sekwencji o niskiej rozbieżności są to rozszerzenia sekwencji van der Corputa na wiele wymiarów. Niech będzie tą najmniejszą liczbą pierwszą. Następnie tego punktu z -wymiarowej sekwencji Halton jest Dla niskiej działają one całkiem dobrze, ale mają problemy z wyższymi wymiarami .$p_j$$j$x i d x i = ( ϕ p 1 ( i ) , ϕ p 2 ( i ) , … , ϕ p d ( i ) $i$$x_i$$d$

$$x_i = (\rinv_{p_1}(i), \rinv_{p_2}(i),\ldots,\rinv_{p_d}(i)) \>.$$ $d$

Sekwencje Halton spełniają . Są również ładne, ponieważ można je rozszerzać , ponieważ konstrukcja punktów nie zależy od a priori wyboru długości sekwencji .$D_n^\star = O(n^{-1} (\log n)^d)$$n$

Sekwencje Hammersleya . Jest to bardzo prosta modyfikacja sekwencji Halton. Zamiast tego używamy Być może zaskakujące jest to, że mają lepszą rozbieżność między .D ⋆ n = O ( n - 1 ( log n ) d - 1

$$x_i = (i/n, \rinv_{p_1}(i), \rinv_{p_2}(i),\ldots,\rinv_{p_{d-1}}(i)) \>.$$ $D_n^\star = O(n^{-1}(\log n)^{d-1})$

Oto przykład sekwencji Halton i Hammersley w dwóch wymiarach.

Faure permutowane sekwencje Halton . Specjalny zestaw permutacji (ustalony jako funkcja ) może być zastosowany do rozszerzenia cyfr dla każdego podczas tworzenia sekwencji Halton. Pomaga to zaradzić (do pewnego stopnia) problemom wskazanym w wyższych wymiarach. Każda z permutacji ma interesującą właściwość utrzymywania i jako punktów stałych.$i$$a_k$$i$$0$$b-1$

Kraty rządzą . Niech będą liczbami całkowitymi. Weź gdzie oznacza ułamkową część . Rozsądny wybór wartości daje dobre właściwości jednorodności. Złe wybory mogą prowadzić do złych sekwencji. Nie można ich również rozszerzać. Oto dwa przykłady.$\beta_1, \ldots, \beta_{d-1}$

$$x_i = (i/n, \{i \beta_1 / n\}, \ldots, \{i \beta_{d-1}/n\}) \>,$$ $\{y\}$$y$$\beta$

$(t,m,s)$ siatki . sieci w bazie są zestawami punktów, tak że każdy prostokąt objętości w zawiera punktów. To silna forma jednolitości. W tym przypadku mały jest twoim przyjacielem. Sekwencje Halton, Sobol 'i Faure są przykładami sieci . Ładnie nadają się do randomizacji poprzez szyfrowanie. Losowe mieszanie (zrobione z prawej) sieci daje inną sieć. Projekt MinT przechowuje zbiór takich sekwencji.$(t,m,s)$$b$$b^{t-m}$$[0,1]^s$$b^t$$t$$(t,m,s)$$(t,m,s)$$(t,m,s)$

Prosta randomizacja: rotacje Cranleya-Pattersona . Niech będzie ciągiem punktów. Niech . Następnie punkty są równomiernie rozmieszczone w .$x_i \in [0,1]^d$$U \sim \mathcal U(0,1)$$\hat x_i = \{x_i + U\}$$[0,1]^d$

Oto przykład z niebieskimi kropkami będącymi oryginalnymi punktami, a czerwonymi kropkami będącymi obróconymi z liniami łączącymi je (i pokazanymi, gdzie to właściwe, owiniętymi wokół).

Sekwencje całkowicie równomiernie rozmieszczone . Jest to jeszcze silniejsze pojęcie jednolitości, które czasem wchodzi w grę. Niech będzie sekwencją punktów w i teraz utworzy nakładające się bloki wielkości aby uzyskać sekwencję . Więc jeśli , bierzemy a następnie itd. Jeśli, dla każdego , , wtedy mówi się, że jest całkowicie równomiernie rozłożony . Innymi słowy, sekwencja daje zestaw dowolnych punktów$(u_i)$$[0,1]$$d$$(x_i)$$s = 3$$x_1 = (u_1,u_2,u_3)$$x_2 = (u_2,u_3,u_4)$ $s \geq 1$$D_n^\star(x_1,\ldots,x_n) \to 0$$(u_i)$wymiar, który ma pożądane .$D_n^\star$

Na przykład sekwencja van der Corputa nie jest całkowicie równomiernie rozłożona, ponieważ dla punkty znajdują się w kwadracie a punkty są w . Stąd nie ma punktów w kwadracie co oznacza, że ​​dla , dla wszystkich .x 2 I ( 0 , 1 / 2 ) x [ 1 / 2 , 1 ) x 2 I - 1 [ 1 / 2 , 1 ) x n ≥ 1 / 4 $s = 2$$x_{2i}$$(0,1/2) \times [1/2,1)$$x_{2i-1}$$[1/2,1) \times (0,1/2)$$(0,1/2) \times (0,1/2)$$s=2$$D_n^\star \geq 1/4$$n$

Standardowe referencje

Niederreiter (1992) monografia i Fang i Wang (1994) tekst są miejsca, aby przejść do dalszej eksploracji.

Jednym ze sposobów jest wygenerowanie jednolitych liczb losowych, a następnie przetestowanie „bliskości” za pomocą dowolnej metody, a następnie usunięcie losowych przedmiotów, które są zbyt blisko innych i wybranie innego zestawu losowych mundurów, aby je nadrobić.

Czy taki rozkład zda każdy test jednorodności? Mam nadzieję, że nie! Nie jest już równomiernie rozprowadzany, jest teraz inną dystrybucją.

Jednym z nieużytecznych aspektów prawdopodobieństwa jest to, że szansa jest zbita. Dane losowe zawierają więcej przebiegów, niż ludzie sądzą. Myślę, że Tversky przeprowadził kilka badań na ten temat (tyle jednak zbadał, że trudno to zapamiętać).

Proces ten nazywany jest „twardym” procesem punktu Poissona - tak nazwany przez Briana Ripleya w latach siedemdziesiątych; tzn. chcesz, aby był losowy, ale nie chcesz, aby punkty były zbyt blisko siebie. „Twardy rdzeń” można wyobrazić jako strefę buforową, wokół której inne punkty nie mogą się wtrącać.

Wyobraź sobie, że rejestrujesz pozycję niektórych samochodów w mieście - ale rejestrujesz tylko punkt w nominalnym środku samochodu. Podczas gdy są na ulicach, dwie pary punktów nie mogą się do siebie zbliżyć, ponieważ punkty są chronione przez „twardy rdzeń” nadwozia - zignorujemy potencjalną super pozycję na parkingach wielopoziomowych :-)

Istnieją procedury generowania takich procesów punktowych - jednym ze sposobów jest po prostu generowanie punktów równomiernie, a następnie usuwanie tych, które są zbyt blisko siebie!

Aby uzyskać szczegółowe informacje na temat takich procesów, patrz na przykład to

W odniesieniu do generowania partii z góry wygenerowałbym dużą liczbę zestawów zmiennych pseudolosowych, a następnie przetestowałem je za pomocą testu takiego jak test Kołmogorowa-Smirnowa. Będziesz chciał wybrać zestaw, który ma najwyższą wartość p (tj. jest idealny). Zauważ, że będzie to powolne, ale wraz ze wzrostem prawdopodobnie stanie się mniej konieczne. $p \approx 1$$N$

Jeśli chodzi o generowanie przyrostowe, zasadniczo szukasz serii z umiarkowanie ujemną autokorelacją. Nie jestem pewien, jaki byłby najlepszy sposób, ponieważ mam bardzo ograniczone doświadczenie z szeregami czasowymi, ale podejrzewam, że istnieją na to algorytmy.

W odniesieniu do testu na „zbyt parzysty”, każdy test na to, czy próbka ma określony rozkład (taki jak wspomniany powyżej KS) zrobi, wystarczy sprawdzić, czy , a nie standardowe podejście. Pisałem tutaj o przykładzie tego alternatywnego podejścia: chi-kwadrat zawsze jest testem jednostronnym . $p > (1-\alpha)$

Sformalizowałbym twój problem w ten sposób: Chcesz rozkład na taki, że gęstość wynosi dla niektórych określających odpychanie punktów. f ( x ) ∝ e ( $[0,1]^n$ k<$f(x) \propto e^{\left(\frac1k\sum_{ij}\lvert x_i-x_j \rvert^{k}\right)^{\frac1k}}$$k<0$

Jednym łatwym sposobem na wygenerowanie takich wektorów jest wykonanie próbkowania Gibbsa.