On the Halton sequence and its scramblings

by syoyo

Bart Vandewoestyne and Ronald Cools
On the Halton sequence and its scramblings
http://www.cs.kuleuven.ac.be/~bartv/downloads/iccam2004_bart_vandewoestyne.pdf

Halton 列の permutation のやり方についての新しい提案。
Halton 列については、高次元になるほど correlation が出てきて、
サンプル点の分布が悪くなることが知られています。

この問題を解決するために、スクランブルをかけて分布
を良くさせます。このときスクランブルに使われる permutation テーブルの
生成のやり方はいろいろと提案されていますが、この文献では、

(0, 1)
(0, 2, 1)
(0, 3, 2, 1)
(0, b – 1, b – 2, …, 1)

という 0 以外は単純に順番を反転させる方法(reverse permutation)を提案しています。

すっげー簡単な方法なのですが、実際これを使うと、今まで提案された
手法よりもなぜか star discrepancy が小さくなって良い分布が
生成されるようです。

lucille では、Alexander Keller の Strictly Deterministic Sampling
にあるように、 Faure の permutation 実装してありますが、
( faure_permutation() )

http://lucille.atso-net.jp/svn/lucille/src/qmc.c

この reverse permutation も試してみたいですね(すごい実装簡単だし)。

Advertisements