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, żenx1, x2), … , Xn[ 0 , 1 ]rereR [ a 1 , b 1 ] × ⋯ × [ a d , b d ]
ren: = supR ∈ R∣∣∣1n∑i = 1n1( xja∈ R )- v o l ( R ) ∣∣∣,
R[ a1, b1] × ⋯ × [ are, bre] 0 ≤ a i ≤ b i ≤ 1 R R R v o l ( R ) = ∏ i ( b i - I )[ 0 , 1 ]re0 ≤ aja≤ bja≤ 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ść , .
RRRv o l (R)= ∏ja( bja- aja)
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 ) Rren( xja)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 = 0
re⋆n= supR ∈ A∣∣∣1n∑i = 1n1( xja∈ R )- v o l ( R ) ∣∣∣.
ZAza1= a2)= ⋯ = are= 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 Are⋆n≤ Dn≤ 2rere⋆nnre
ZA⊂ R.R ∈ R2)reZA
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 nrenre⋆nn
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 .re⋆n
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 - 1re= 1jabi = ∑ ∞ k = 0 a k b k a k b i 41 101001 a 0 = 1
ϕb( i ) = ∑k = 0∞zakb- k - 1,
i = ∑∞k = 0zakbkzakbja41101001za0= 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 ) = 0,100101za1= 0za2)= 0za3)= 1za4= 0za5= 1x41= ϕ2)( 41 ) = 0,100101(podstawa 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 .ja1 x I I [ 1 / 2 , 1 ) x I I ( 0 , 1 / 2 )01xjaja[ 1 / 2 , 1 )xjaja( 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 . jpjotjotx i d x i = ( ϕ p 1 ( i ) , ϕ p 2 ( i ) , … , ϕ p d ( i ) )jaxjarere
xja= ( ϕp1( i ) , ϕp2)( i ) , … , ϕpre( i ) ).
re
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 .nre⋆n= O ( n- 1( logn )re)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 )
xja= ( i / n , ϕp1( i ) , ϕp2)( i ) , … , ϕpre- 1( i ) ).
re⋆n= O ( n- 1( logn )re- 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.jazakja0b - 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.β1, … , Βre- 1
xja= ( i / n , { i β1/ n},…,{i βre- 1/ n}),
{ y}yβ
( 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 )bbt - m[ 0 , 1 ]sbtt( 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 .xja∈ [ 0 , 1 ]reU∼ U( 0 , 1 )x^ja= { xja+ U}[ 0 , 1 ]re
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( uja)[ 0 , 1 ]re( xja)s = 3x1= ( u1, u2), u3))x2)= ( u2), u3), u4) s ≥ 1re⋆n( x1, … , Xn) → 0( uja)wymiar, który ma pożądane .re⋆n
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 ns = 2x2 i( 0 , 1 / 2 ) x [ 1 / 2 , 1 )x2 i - 1[ 1 / 2 , 1 ) x ( 0 , 1 / 2 )( 0 , 1 / 2 ) x ( 0 , 1 / 2 )s = 2re⋆n≥ 1 / 4n
Standardowe referencje
Niederreiter (1992) monografia i Fang i Wang (1994) tekst są miejsca, aby przejść do dalszej eksploracji.