数理解析研究所講究録1032 巻 1998 年 125-128125$\mathrm{W}\mathrm{e}\mathrm{y}$I 列と Va$\mathrm{n}$$\mathrm{d}\mathrm{e}r$$\mathrm{C}\mathrm{o}\mathrm{r}\mathrm{p}\mathrm{u}\mathrm{t}$On W 伽\not\equiv s qu 伽 noes and Van d 伽 r Co\mbox{\boldmath $\varphi$}火$\mathrm{S}$列について

q 火 enc$\mathrm{S}$

手塚集

日本アイビーエム東京甚礎研究所(Shu Tezuka)

1 。はじめに今日使われている low-discrepancy sequenoe8 は、 2 つのタイプに分類される。 -つはWeyl 列 $\{na\},$ $n\#$,l,2lg.a’ から派生したもので、 その系統として、 Richtmyer 列がある。
ここで、$\alpha$は無理数であるとし、記号 $\{\}$ は小数部分のみをとることを意味している。

もうひとつは Van der Corput 列直 n),n=0,1,2,..., の–般化である。ここで、$\emptyset$

は基底 2radical inveaee function を意味する。 この系統では、 Halton 列をはじめ (t,8)-列 (これは Sobol, Faure, および –般化 Niederreiter 列を含む非常に広いクラス) が属していのる。

ここでは、この 2 つの異なる 1 次元観点から論じたい。 1 つは

$1_{\mathrm{o}\mathrm{W}-}\mathrm{d}\mathrm{i}\mathrm{S}\mathrm{c}\mathrm{r}\mathrm{e}_{\mathrm{P}\mathrm{c}8\mathrm{e}}\mathrm{a}\mathrm{n}\mathrm{y}\mathrm{q}\mathrm{u}\mathrm{e}\mathrm{n}\mathrm{C}\mathrm{e}\mathrm{s}$$\mathrm{G}\mathrm{F}\{2, \mathrm{z}\}$構成される体) での Van der$\mathrm{c}_{\mathrm{o}\mathrm{r}_{\mathrm{P}^{\mathrm{u}\dot{\mathrm{t}}}}}$(の類似点について 2 つの(2) 上の形式的ローラン展開により$\mathrm{G}\mathrm{F}$興及び Weyl 列のアナロジーという観点である。 ここでは、 2 つの数列の違いは生成行列の違いとして現れてくる。もう一つの観点は、Weyl列め連分数近似に基づくものである。 $a$ として、黄金分割比を用いた場合について解析する。 この場合はフィボナッチ数体系における Van der Corpul 列との著しい共通点が存在することが示される。

2 。定義
まず、

$\mathrm{d}\mathrm{i}_{8\mathrm{c}\mathrm{r}}\mathrm{e}\mathrm{p}\mathrm{a}\mathrm{n}\mathrm{C}\mathrm{y}$の定義は次のように与えられる(文献$2_{\text{、}}$

$3$

参照)

。

(定義)
$\mathrm{k}$次元単位立方体内の$J= \prod_{t=1}k\mathrm{I}\mathrm{o},u)i$定義する。

$\mathrm{N}$

偲の点$\chi_{0},\chi\ldots,$$(\text{ここで}0<u_{i}\leq 1,1\leq i\leq k)$$1’$XN-1 に対して、$\mathrm{k}\geq 1$としたとき、 次のようにかつ部分区間

crepancy を$\mathrm{d}\dot \mathrm{o}\mathrm{e}$126$D_{N}^{(k)}= \sup_{J}|\frac{A(J,N)}{N}.-V\mathit{0}l(J)|$

ここで、 A(J;N は $X_{n}\in J$ となる $n,0\leq n<N$ , の数で、 Vol(J) は蔀分区間$\rangle$$8\mathrm{u}\mathrm{p}oe$$\mathrm{k}$mum はすべての$\mathrm{J}$$\mathrm{N}$の体積、またについてとることにする。 口

次元単位立方体内の無限点列

頭の$\mathrm{J}$$x_{0},\dot{\chi}_{1},\ldots,X_{N1}-,\ldots$

はもしすべてのに対して、 先$\mathrm{N}>1$

点の discrepancy が$D_{N}^{\{k)} \leq C_{k}\frac{(\log N)k}{N}$を満たすならば、 low-discrepancy sequenoe と呼ばれる。 ここで、

$C_{k}$は次元$\mathrm{k}$のみに依る定数である。
また、 フィボナッチ数体系 (文献 1 参照) とは次のようなものである :$F\tilde{.},i=0,1,2,\ldots$, をフィボナッチ数とする。 つまり、 $F_{0}=0,F_{\iota^{=}}1$ で、 $F_{i+1}=F+Fl \int-\iota$ を満足する数列である。 すると、 非負整数$\mathrm{n}$は次のような形に–意に表現できる。

$n=a_{0}F_{2}+a_{1}F_{3^{+}}\cdots+a_{\mathrm{t}-}3F_{\iota_{-}1}$

ここで、 $a_{k-3}$ は $0$ ではないとする。

すると、 Van der Corput 列, 貞 n),n $=0,1,2,\ldots$ ,$n=aF_{2^{+}}\mathit{0}aF_{\mathrm{a}}\star\cdot\cdot+\iota a_{k-3}F_{k-1}$は次のように–般化できる。 非負整数とすると、$\psi(n)=.\frac{OF+aFo0\iota-\iota 1k-2^{+\cdots+F_{2}}k-3}{F_{k}}$となる。
ここで、 $F_{i}=2^{i-2}$ とすれば、 $\psi(n)$ が基底 2 の radical inverse fumetion 貞 n) と –致していることは容易にわかる。

3$\mathrm{G}\mathrm{F}$。

非負整数$\mathrm{n}(\mathrm{z})$$\{2, \mathrm{z}\}$$\mathrm{n}$におけるアナロジーという観点.の 2 進展開を $n=n_{0}+n_{1}2+n_{2}2^{2}\star\cdot$ とする。 その時、を $n_{0}+n_{12}z+nz^{2}+\cdots$ と定義する。 また、うなものを選び$\mathrm{G}\mathrm{F}\{2, \mathrm{z}\}$$\mathrm{a}(\mathrm{z})=a_{1}z^{-}1+O_{2^{\overline{\angle}^{-2}}}+aZ-3+3\ldots$$\rangle$$\mathrm{G}\mathrm{F}.(.2$.

.

上の多項式内の元で deg(a) $<0$ となるよとおく。 Weyl 列のアナロジーから、 次のような数列が定義できる。
$W_{n}\langle\phi=\{\mathrm{n}(_{\mathrm{Z}}\rangle \mathrm{a}(\mathrm{Z})\}$。

ここで$\{$$\}$

は小数部分 (次数が負の部分\rangle のみを残す操作を意味している。

$W_{n1}Z^{-1}+w_{n2}Z^{-2}+w_{n3}z^{-}+3\ldots$とすると、 行列表現により、$W_{n}(\mathrm{z})=$127$w_{\hslash}w_{\hslash 1}w_{n3}2)=\{aa_{2}a_{3}1$$a_{2}a_{3}a_{4}$$a_{3}a_{4}a_{5}$$.\cdot.\cdot..\cdot..||_{n}^{n_{0}}n_{1}2$

この場合に [0,11 内の数列をと表すことができる。 つまり$w_{n1}2^{-\mathrm{t}}+w_{n2}2^{-2}+w_{n3}2^{-3}+\cdots$ と定義すれば、 これは (t,k 列とよばれる数列であることが$W_{n}(\mathit{2}\rangle=$$\text{、}$$\rangle$わかる。さらにここで用いられる生成行列は Hankel 行列とよばれる特殊な対称行列になにおけるアナロジー列のっていることが示せる。 また、 Van$\mathrm{G}\mathrm{F}\{2.’$\mathrm{d}\mathrm{e}t.\mathrm{c}_{0}\mathrm{r}\mathrm{P}^{\mathrm{u}\mathrm{t}}$\mathrm{z}\}$については、 すでに文献 3 で解析されており、 この場合も (t,k) 列とよばれる数列になることが知られている。 しかし、 その時現れる生成行列は対称行列ではあるが、 Hankel 行列とはならないことがわかっている。 つまり、$\mathrm{G}\mathrm{F}\{2, \mathrm{z}\}$におけるアナロジーという観点では、 どちらの数列も (t,k) 列に分類され、 生成行列の性質にのみ違いが生じているということになる。

4。

Weyl 列の連分数近似という観点

Weyl 列は$W_{n}=\{n\alpha\},$ $n=1\mathit{2},\ldots$, において $a=(1+\sqrt{5})/2$ とした時がもっとも–様である事が知られている。 ここで、 $a$ は黄金分割比であり、 記号 $\{\}$ は実数の小数部分をとることを意味している。 また、 その連分数近似を用いて次のような近似数列, が考えられる。 つまり、 $F_{k-1}\leq n<F_{k}$ に対して,$\overline{W_{n}},n=1\mathit{2},\ldots$$\overline{W_{n}}=\mathrm{f}\frac{F_{k-1}(a_{0}F+\cdots a2k-3k-F\rangle 1}{F_{k}}\}$とするのである。 ここで、,$(1\rangle$$n=a_{0}F_{2}+aF13+\cdots+aFk-3k-\iota$ であり、 また $a_{k-3}$いとする。 その時次の定理が成り立つ。
(定理)$n=a_{\mathit{0}}F_{2^{+a}}\mathrm{I}F_{3^{+}}\cdot\cdot+aF_{k}k-3-1$とした時、$\overline{W_{n}}=\frac{(-1)_{\mathit{0}_{0}}F_{k-}\cdot\cdot+(2^{+}-\iota)k- 2F_{1}a_{k-3}}{F_{k}}$mod$\langle$である。 口(証明)

まず、 O\leq i\leq k-l に対して、$F_{k-1}F\iota=F_{\iota-1}F_{i}+F_{k}Fi+\iota=F_{k+i}$である。 また、$1\leq i$に対して、(mod$F_{k}$)$1\rangle$

は $0$ ではな

128

$F_{\iota+i}=h_{t}F_{\iota^{+()F}}-1i-1k-i$が成り立つ。 ここで、’

$h_{1}=\iota,h=3,\text{及び}$$F_{k+i}=(-1)^{i-}1F_{k-}i$$h_{\tilde{l}}=h_{i-1^{+}}h_{i-2}$である。 ゆえに$(\mathrm{m}\mathrm{o}\mathrm{d} F_{k})$となり、 これを (1) 式の右辺分子に代入することにより、 証明が完了する。
口

ここで注意することは、$\frac{F_{k-1}}{F_{k}}\leq\frac{(-1)a_{0^{F_{k-2^{+}}}}\cdots+(-1)^{k-2}aF_{1}k\sim 3}{F_{k}}\leq\frac{F_{k\sim 2}}{F_{k}}=1-\frac{F_{k-1}}{F_{k}}$である。 つまり (mod 1) は大した役割はしておらず、 区間 [$0,11^{\text{が}}-F_{k-1}/F_{k}$ ずれたにすぎない。 また分子をよくみると第 2 節で定義したフィボナッチ数体系におけるVan derCorput 列の場合と良くにていることがわかる。実際、 $(-1)$ の項がついていることと添え字が $k-2$ から始まることを除けば本質的にはかわらない。つまり、一様性を生み出す構造はどちらも同じになっている。

参考文献

1.

D. E. Knuth, The Art of Computer Programming,$\mathrm{V}\mathrm{o}\mathrm{L}2$, Second Edition,-Wesley, 1981.

$\mathrm{A}\mathrm{d}\mathrm{d}\mathrm{i}_{8}\mathrm{o}\mathrm{n}$2.

3.

H. Niederreiter, Random Number Generation andonte Carlo
Methods, SIAM, Phfladelphia, Penn., 1992.
S. Tezuka, Uniform Random Numbers : Theory and Practice, Kluwer$\mathrm{q}_{\mathrm{u}\mathrm{a}8\mathrm{i}}$Acadenic$\mathrm{P}\mathrm{u}\mathrm{b}\Re \mathrm{h}\mathrm{e}\mathrm{r}6$, Boelon, 1995.