ハルトンシーケンス

統計学において、ハルトン数列は、モンテカルロシミュレーションなどの数値計算法で空間に点を生成するために使用される数列です 。これらの数列は決定論的ですが、矛盾は少なく、多くの目的においてランダムであるように見えます。これらは 1960 年に初めて導入され、準乱数列の例です。これらは 1 次元のファンデルコルプ数列を一般化します。

ハルトン数列は互いに素な数を基数とする決定論的手法によって構築されます。簡単な例として、2次元ハルトン数列の1つの次元を2に、もう1つの次元を3にしてみましょう。2の数列を生成するには、まず区間(0,1)を半分に分割し、次に4分の1、8分の1などに分割します。

1 ⁄ 2、

1 ⁄ 4、 3 ⁄ 4、

1 ⁄ 8、5 ⁄ 8、3 ⁄ 8、7 ⁄ 8、​​​​​​

1 ⁄ 16、9 ⁄ 16 、 ...​

同様に、この数列の n 番目の数は、2 進数で表された数 n を反転し、小数点の後に書きます。これは、どの基数にも当てはまります。たとえば、上記の数列の 6 番目の要素を見つけるには、6 = 1*2 ² + 1*2 ¹ + 0*2 ⁰ = 110 ₂と書きます。これを反転して小数点の後に書き込むと、0.011 ₂ = 0*2 ^-1 + 1*2 ^-2 + 1*2 ^-3 = 3 ⁄ 8になります。したがって、上記の数列は次のようになります。

0.1 ₂、0.01 ₂、0.11 2 _、 0.001 ₂、0.101 ₂、0.011 ₂、0.111 2 、0.0001 ₂、0.1001 _{2 、} ...

他の次元の3のシーケンスを生成するには、区間(0,1)を3分の1、9分の1、27分の1などに分割し、次の数を生成します。

1 ⁄ 3、2 ⁄ 3、1 ⁄ 9、4 ⁄ 9、7 ⁄ 9、2 ⁄ 9、5 ⁄ 9、8⁄ 9、1 ⁄ 27、 ...​​​​​​​​​​​​​​​

これらをペアにすると、単位正方形内の点の列が得られます。

( 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 )。

標準的なハルトン シーケンスは低次元では非常にうまく機能しますが、より高い素数から生成されたシーケンス間では相関の問題が指摘されています。たとえば、素数 17 と 19 から始めた場合、最初の 16 組のポイント: ( 1 ⁄ 17、1 ⁄ 19 )、( 2 ⁄ 17、2 ⁄ 19 )、( 3 ⁄ 17、3 ⁄ 19 ) ... ( 16 ⁄ 17、16 ⁄ 19 ) は完全な線形相関を持ちます。これを回避するには、最初の 20 エントリを削除するか、選択した素数に応じて他の事前に決定された量を削除するのが一般的です。他の方法もいくつか提案されています。最も有名な解決策の 1 つは、標準シーケンスの構築に使用される係数の順列を使用するスクランブル ハルトン シーケンスです。もう 1 つの解決策は、標準シーケンス内のポイントをスキップするリープ ハルトンです。例えば、409番目のポイントのみを使用すると（ハルトンコアシーケンスで使用されていない他の素数も可能）、大幅な改善が達成できます。^[1]

疑似コードでは:

アルゴリズムHalton-Sequenceは
    入力:インデックス
            ベース出力:結果です${\displaystyle i}$${\displaystyle b}$
    ${\displaystyle r}$

    ${\displaystyle f\leftarrow 1}$
    ${\displaystyle r\leftarrow 0}$

     しながら${\displaystyle i>0}$ 
        ${\displaystyle f\leftarrow f/b}$
        ${\displaystyle r\leftarrow r+f*(i\operatorname {mod} b)}$
        ${\displaystyle i\leftarrow \lfloor i/b\rfloor }$

    戻る ${\displaystyle r}$

基数bのハルトン数列の連続する数を生成する別の実装は、次のジェネレータ関数（Python）で与えられます。^[2]このアルゴリズムは内部的に整数のみを使用するため、丸め誤差に対して堅牢です。

def  halton_sequence ( b ): 
"""ハルトンシーケンスの生成関数。""" n , d = 0 , 1 while True : x = d - n if x == 1 : n = 1 d *= b else : y = d // b while x <= y : y //= b n = ( b + 1 ) * y - x yield n / d    
        
     
            
           
              
              
        
                
               
                  
                    
           

• 低矛盾シーケンスの構築

• カイパーズ、L. Niederreiter, H. (2005)、配列の均一分布、Dover Publications、p. 129、ISBN 0-486-45019-8
• Niederreiter、Harald (1992)、乱数生成と準モンテカルロ法、SIAM、p. 29、ISBN 0-89871-295-5。
• Halton, J. (1964)、「アルゴリズム 247: ラジカル逆準ランダム点列」、Communications of the ACM、7 (12): 701-701、doi : 10.1145/355588.365104、S2CID  47096908。
• Kocis, Ladislav; Whiten, William (1997)、「低矛盾シーケンスの計算調査」、ACM Transactions on Mathematical Software、23 (2): 266–296、doi : 10.1145/264029.264064、S2CID  183263。