Halton Sequence

Halton 数列は、互いに素な 2 つの底を使った Van der Corput 数列を組み合わせた 2 次元の低差異数列です。一見ランダムに見える点が、実は均一に分布するように設計されています。

定義

底 $b_1, b_2$ が互いに素なとき、Halton 数列は次のように定義されます。

P_n = \\bigl( \\phi_{b_1}(n), \\phi_{b_2}(n) \\bigr)

ここで $\\phi_b(n)$ は底 $b$ の Van der Corput 数列です。

点数256

$b_x=2, b_y=3$

$b_x=2, b_y=5$

$b_x=3, b_y=5$

4×48×816×16

単位正方形を $8 \times 8$ のグリッドで分割し、各セルに入る点数のばらつきを比較します。値が小さいほど均一です。

底の組み合わせ	最大偏差	標準偏差
Halton $(2, 3)$	0.39%	0.23%
Random $(2, 3)$	1.56%	0.61%
Halton $(2, 5)$	0.39%	0.17%
Random $(2, 5)$	1.56%	0.61%
Halton $(3, 5)$	1.17%	0.44%
Random $(3, 5)$	1.56%	0.61%

この一様性が数値積分の収束速度にどう効くかは Monte Carlo 収束速度比較で扱っています。

底の組み合わせが互いに素でないと、点が規則的な格子状に並んでしまい、一様性が損なわれます。通常は異なる素数を選びます。