low discrepancy sequence の構成

森 真
日本大学文理学部

2001年11月27日

$[0,1]^d$ $(d\ge1)$の上の列 $x_1,x_2,\ldots$が一様分布列であるとは 任意の区間 $J\subset [0,1]^d$について

$$\lim_{n\to\infty}\left\vert{\char93 \{x_n\in J\colon n\le N\}\over N}-\vert J\vert\right\vert=0$$

が成り立つことである。ここで$\vert J\vert$は$J$のルベーグ測度を表す。 一様分布列は数値積分の擬Monte Carlo法に用いられるが その収束が早いものが望まれる。収束の早さはそのdiscrepancy $D(N)$ によって評価され、

$$\left\vert\int f(x)\,dx-{f(x_1)+\cdots+f(x_N)\over N}\right\vert\le V(f)D(N)$$

であることが示されている。ここで$V(f)$は$f$の全変動を表す。 したがって、discrepancyの小さい列を構成することが重要になってくる。 一様分布列のdiscrepancy $D(N)$は

$$D(N)=\sup\left\vert{\char93 \{x_n\in J\colon n\le N\}\over N}-\vert J\vert\right\vert$$

で定義される。これは

$$D(N)=O\left({(\log N)^d\over N}\right)$$

をみたすとき、一様分布列はlow discrepancy であるという。 $d=1,2$のときには、$D(N)$はlow discrepancy 列より収束が良く ならないことが証明されていて、$d\ge3$でも成り立つであろうと予想 されている。1次元の場合に有名なlow discrepancy列として$n$進法を用いた van der Corput列があげられる。これを二宮氏は$\beta$展開の場合に 拡張した。それを力学系の視点から見直すことで、一般の1次元piecewise linear変換の場合にその逆像を用いて構成した列について次の 定理が示される。

定理 1   $F$を1次元のpiecewise linearかつ傾きが一定: $\vert F'\vert=\beta>1$かつtopologically transitiveとする。このとき、

1. $F$に対応するPerron-Frobenius operatorが固有値を$1/\beta<\vert z\vert<1$ に持たないときには、任意の$\varepsilon>0$について $D(N)=O(N^{-1-\varepsilon})$である。とくに、$F$がMarkovならば、 low discrepancyである。
2. もし、上の円環内に固有値を持てば、正の確率で$x$について 列はlow discrepancyではない。

高次元の場合にはperron-Frobenius operatorのessential spectrum radiusが 大きくなってしまうので、一般論を用いることができない。そこで、 特殊な変換を構成して2次元の場合のlow discrepancy列を構成する