低食い違い数列の基礎

先日無知を晒した低食い違い数列について少し勉強しました。

Van der Corput sequence

Van der Corput sequenceは、最もシンプルで、0~1の範囲に分布する、1次元の低食い違い数列と言われているそうです。
基数:b表現されたの自然数の数列の各桁を反転させることで作ることができます。基数bで表現される正の整数nは、
\begin{aligned}  n=\sum_{k=0}^{L-1}{d_k(n)b^k}   \end{aligned}
で表現されます。bは基数で、kは桁の位置を表し、d_k(n)は、その桁の数を表します。10進数の3桁目なら、b^kは100となり、その位の数(0~9)と乗算すれば3桁目の数の表す数の大きさが計算できるので、これを全部の桁であるL桁まで計算して、総和をとればその数になるというわけです。

これに対応する、Van der Corpt sequenceの表現は下記の通りになります。
\begin{aligned}  g_b(n)=\sum_{k=0}^{L-1}{d_k(n)b^{-k-1}}   \end{aligned}
先ほどの例で、nにおける10進数3桁目に対応するg_b(n)は、10^-3となり、1/1000に相当します。
また、具体例を挙げるとすれば、十進数の自然数1234に対応するg_b(n)は、0.4321となります。
同様に数列で例を挙げると以下のようになります。

n : (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23)
g_b(n) : (0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 0.01, 0.11, 0.21, 0.31, 0.41, 0.51, 0.61, 0.71, 0.81, 0.91, 0.02, 0.12, 0.22, 0.32)

特長としては、基数の数だけ自然数が並べば、素早く[0, 1)の範囲に等しく分布し、その後も、決して他の数に重複することなく分布することだと思います。
欠点は、用いる基数が大きいと、連続した数列を入力とした場合に、互いの差が、ほぼb^1となってしまい、線形性が強くみられることでしょうか。
また、連続するVan der Corput sequenceを、そのままベクトル要素として並べて多次元拡張すると、多次元空間において一様(といえるような)な分布とはなりません。例えば、基数2のVan der Corput sequenceは、奇数番目では、必ず1/2より大きく、偶数番目では1/2より小さいなどの規則性があり、これを2次元空間でそのまま並べて使うと、一様に近い分布を得ることができません。

Halton sequence

Halton sequenceは、互いに素な基数の、複数のVan der Corput 列を、必要な次元数分並べたベクトルになります。Van der Corput sequenceの、他の値に重ならないという特徴を維持したまま、多次元拡張したものといえるかもしれません。
具体的な例として、2次元の場合で、基数に、2と3を用いた例では以下のようになります。

g2(n) : (1/2, 1/4, 3/4, 1/8, 5/8...)
g3(n) : (1/3, 2/3, 1/9, 4/9, 7/9...)
Halton(2,3) :  (1/2, 1/3), (1/3, 2/3), (3/4, 1/9), (1/8, 4/9), (5/8, 7/9)

特長と欠点は、Van der Corput sequenceと同様で、大きな基数を用いると、連続した自然数の入力に対して、線形性が見られます。

Hammersley Point Set

Hammersleyは、有限個の点群であるという前提があるので、数列と呼ばずに、点群と呼びます。Halton sequenceとの大きな違いは、ベクトル要素の一つを、Van der Corput sequenceを用いずに求めることです。
まず、点群の総数をNとして定義します。入力は0~N-1の範囲とします。入力をiとするするとき、ベクトルの一つの要素を、i/Nで求めます。他の要素は、Halton sequenceと同様に、複数のVan der Corput 列を、必要な次元数分用います。

特長は、ベクトルの一要素を単純な計算で算出できることと、詳しくは理解していませんが、Halton sequenceよりもLow Discrepancyだと、他で記されています。
欠点は、初めに点群の個数を定義しないといけないので、インクリメンタルに点群を増やすことができません。また、点群の個数を大きく取り、実際に使用するサンプルを少なく、偏った自然数からサンプルした場合は、Van der Corput sequenceを用いずに求めた要素に、明らかな偏りが生じるので、必要なサンプル数で、点群の個数を定義する必要があります。

特に、2次元のHammersley Point Setで、点群の総数を2のべき乗として、基数2のVan der Corput sequenceを用いると、x=yで対称な分布となります。また、この際に、下位の桁を切り捨てていくと、最終的には等間隔のグリッド上に等しい数のサンプルが集約するようになります。これは、binary(t, m, s)-netとして知られているそうです。(sは次元数、tは切り捨てる下位ビットの数、mは点群の総数の2のべき乗の乗数)

以下に点群数16、次元数2の場合で、基数2のHammersley Point Setの、下位ビットを切り捨てていった場合の値の推移を示します。

binary(0, 4, 2)-net
(0,  8/16,  4/16, 12/16,  2/16, 10/16,  6/16, 14/16,  1/16,  9/16,  5/16, 13/16,  3/16, 11/16,  7/16, 15/16)
(0,  1/16,  2/16,  3/16,  4/16,  5/16,  6/16,  7/16,  8/16,  9/16, 10/16, 11/16, 12/16, 13/16, 14/16, 15/16)

binary(1, 4, 2)-net
(0,  4/8,  2/8,  6/8,  1/8,  5/8,  3/8,  7/8,  0/8,  4/8,  2/8,  6/8,  1/8,  5/8,  3/8,  7/8)
(0,  0/8,  1/8,  1/8,  2/8,  2/8,  3/8,  3/8,  4/8,  4/8,  5/8,  5/8,  6/8,  6/8,  7/8,  7/8)

binary(2, 4, 2)-net
(0,  2/4,  1/4,  3/4,  0/4,  2/4,  1/4,  3/4,  0/4,  2/4,  1/4,  3/4,  0/4,  2/4,  1/4,  3/4)
(0,  0/4,  0/4,  0/4,  1/4,  1/4,  1/4,  1/4,  2/4,  2/4,  2/4,  2/4,  3/4,  3/4,  3/4,  3/4)

このことから、2次元の、基数2のHammersley Point Setを2のべき乗個の点群は、良好な分布を持っていることがわかります。

終わりに

他にも低食い違い数列のアルゴリズムはありますが、今回はここまで。
必要に応じて適宜勉強していきたいと思います。

参照
[lucille 開発日記]2003年08月14日 準モンテカルロ法
http://lucille.sourceforge.net/blog/archives/cat_aaaaaa.html
Van der Corput sequence
https://en.wikipedia.org/wiki/Van_der_Corput_sequence
Hammersley Point Set
http://mathworld.wolfram.com/HammersleyPointSet.html
Strictly Deterministic Sampling Methods in Computer Graphics[Alexander Keller]

広告