Sekwencja Haltona

256 punktów z pierwszych 256 punktów sekwencji Haltona 2,3 (na górze) w porównaniu ze źródłem liczb pseudolosowych (na dole). Sekwencja Haltona pokrywa przestrzeń bardziej równomiernie. (czerwony=1,...10, niebieski=11,...100, zielony=101,...256)

W statystyce sekwencje Haltona są sekwencjami używanymi do generowania punktów w przestrzeni dla metod numerycznych, takich jak symulacje Monte Carlo . Chociaż te sekwencje są deterministyczne , mają niewielką rozbieżność , to znaczy wydają się być losowe z wielu powodów. Zostały one po raz pierwszy wprowadzone w 1960 roku i są przykładem quasi-losowej sekwencji liczb. Uogólniają jednowymiarowe sekwencje van der Corput .

Przykład sekwencji Haltona użytej do wygenerowania punktów w (0, 1) × (0, 1) w R ²

Ilustracja pierwszych 8 punktów ciągu 2,3 ​​Haltona

Sekwencja Haltona jest konstruowana zgodnie z metodą deterministyczną, która wykorzystuje liczby względnie pierwsze jako podstawy. Jako prosty przykład przyjmijmy, że jeden wymiar ciągu Haltona jest oparty na 2, a drugi na 3. Aby wygenerować ciąg dla 2, zaczynamy od podzielenia przedziału (0,1) na pół, następnie na czwarte, ósemki itp., który generuje

1 / 2 ,

1 / 4 , 3 / 4 ,

1 / 8 , 5 / 8 , 3 / 8 , 7 / 8 ,

1 / 16 , 9 / 16 , ...

⁰ Równoważnie, n-tą liczbą tego ciągu jest liczba n zapisana w postaci binarnej, odwrócona i zapisana po przecinku. Dotyczy to dowolnej bazy. Na przykład, aby znaleźć szósty element powyższej sekwencji, zapisalibyśmy 6 = 1*2 2 ⁺ 1*2 ¹ + 0*2 = 110 ₂ , co można odwrócić i umieścić po przecinku, aby uzyskać 0,011 ₂ = 0*2-1 ⁺ 1*2-2 ⁺ 1* ^2-3 = 3 ⁄ 8 . Więc sekwencja powyżej jest taka sama jak

0,1 ₂ , 0,01 ₂ , 0,11 ₂ , 0,001 2 _, 0,101 _{2 , 0,011 2} , 0,111 ₂ , 0,0001 ₂ , 0,1001 ₂ ,...

Aby wygenerować sekwencję dla 3, dzielimy przedział (0,1) na tercje, następnie dziewiąte, dwudzieste siódme itd., co generuje

1 / 3 , 2 / 3 , 1 / 9 , 4 / 9 , 7 / 9 , 2 / 9 , 5 / 9 , 8 / 9 , 1 / 27 , ...

Kiedy połączymy je w pary, otrzymamy ciąg punktów w kwadracie jednostkowym:

( 1 / 2 , 1 / 3 ), ( 1 / 4 , 2 / 3 ), ( 3 / 4 , 1 / 9 ), ( 1 / 8 , 4 / 9 ), ( 5 / 8 , 7 / 9 ), ( 3 / 8 , 2 / 9 ), ( 7 / 8 , 5 / 9 ), ( 1 / 16 , 8 / 9 ), ( 9 / 16 , 1 / 27 ).

Chociaż standardowe sekwencje Haltona działają bardzo dobrze w małych wymiarach, zauważono problemy z korelacją między sekwencjami wygenerowanymi z wyższych liczb pierwszych. Na przykład, jeśli zaczęliśmy od liczb pierwszych 17 i 19, pierwszych 16 par punktów: ( 1 / 17 , 1 / 19 ), ( 2 / 17 , 2 / 19 ), ( 3 / 17 , 3 / 19 ) . .. ( 16 / 17 , 16 / 19 ) miałby idealną korelację liniową . Aby tego uniknąć, często odrzuca się pierwsze 20 wpisów lub inną z góry określoną liczbę w zależności od wybranych liczb pierwszych. Zaproponowano również kilka innych metod. Jednym z najbardziej znanych rozwiązań jest zaszyfrowana sekwencja Haltona, która wykorzystuje permutacje współczynników użytych do budowy sekwencji standardowej. Innym rozwiązaniem jest skaczący Halton, który pomija punkty w standardowej sekwencji. Używając np. tylko każdego 409. punktu (możliwe są też inne liczby pierwsze nie używane w ciągu rdzenia Haltona), można osiągnąć znaczną poprawę.

Realizacja

W pseudokodzie:

    
    

    
    

      
        
         algorytm  Halton-Sekwencja  to  dane wejściowe  : indeks ${\ displaystyle i}$ podstawa ${\ displaystyle b}$ wyjście  : wynik ${\ displaystyle r}$${\ displaystyle f \ leftarrow 1}$${\ displaystyle r \ leftarrow 0 }$ podczas gdy ${\ Displaystyle i> 0}$ zrobić ${\ Displaystyle f \ leftarrow f/b}$
        

     ${\ Displaystyle r \ strzałka w lewo r + f * (i \ nazwa operatora {mod} b)}$${\ Displaystyle i \ strzałka w lewo \ lfloor i/b \ rfloor}$ powrót ${\ displaystyle r}$

Alternatywna implementacja, która tworzy kolejne liczby sekwencji Haltona dla podstawy b , jest podana w poniższej funkcji generatora (w Pythonie ). Algorytm ten używa wewnętrznie tylko liczb całkowitych, co czyni go odpornym na błędy zaokrągleń.

 
    
       0 
     
            
           
              
              
        
                
               
                  def  halton_sequence  (  b  ):  """Funkcja generatora dla ciągu Haltona."""  n  ,  d  =  ,  1  while  True  :  x  =  d  -  n  if  x  ==  1  :  n  =  1  d  *=  b  else  :  y  =  d  //  b  podczas gdy  x  <=  y  :  y  //=  
                    
            b  n  =  (  b  +  1  )  *  y  -  x  wydajność  n  /  re 

Zobacz też

• Konstrukcje ciągów o małej rozbieżności

•   Kuipers, L.; Niederreiter, H. (2005), Jednolity rozkład sekwencji , Dover Publications , s. 129, ISBN 0-486-45019-8
•   Niederreiter, Harald (1992), Generowanie liczb losowych i metody quasi-Monte Carlo , SIAM , s. 29, ISBN 0-89871-295-5 .
•   Halton, J. (1964), "Algorithm 247: Radical-inverse quasi-random point sequence", Communications of the ACM , 7 (12): 701-701, doi : 10.1145/355588.365104 , S2CID 47096908 .
•   Kocis, Władysław; Whiten, William (1997), „Computational Investigations of Low-Discrepancy Sequences”, ACM Transactions on Mathematical Software , 23 (2): 266–296, doi : 10.1145/264029.264064 , S2CID 183263 .