13.超一様分布列とその応用

超一様分布列(Low-discrepancy sequence=低くい違い列, 昔は「準乱数列」と呼ばれていた)とは, 定積分の数値を高速に求めるために工夫された特殊な無限列であり, 「乱数らしさ」は一切要求されていない.

その起源は

定積分の数値を求めるには少なくとも3つの方法がある. 定積分を次のように近似する場合,

(f(x1)+...+f(xN))/N ≒[0,1]s f(x) dx

標本点 x1, ..., xN ∈[0,1]s の取り方により計算法が変わってきます.

数値積分法 x1, ..., xN  食い違い度  xN+1 を計算するにあたり
x1, ..., xN を取り直す必要性
台形則・シンプソン則(11/20) 等間隔(図参照) 低い あり
モンテカルロ法(11/13) 擬似乱数列 必ずしも低くない なし
準モンテカルロ法(11/20) 超一様分布列 低い なし

図. 3次元の格子点

台形則やシンプソン則では, 一番近い標本点との距離を2分の1にすると(刻みを2倍に細かくすると),
標本点の個数Nが 2s 倍になり, コンピュータで計算する際の困難の一つである(次元の呪いという).




定義(Discrepancy(くい違い度))

Niederreiterの記法を使用する.
s は正整数とする.  [0, 1)s の数列P =x1, …, xN の Star-Discrepancy は以下の通り定義されます.



λs(B) はBのs次元での「体積」

集合 Bに対して

A(B; P) := Bに属するPの中の点の個数.

J* :={  [0, u1)×...× [0, us)| 0 ≦ u1, ..., us < 1 }



Koksma-Hlawka不等式

Is を s次元の単位立方体 [ 0, 1]s とする.

f の Hardy と Krause の意味での変動を V(f) と
すると, どんな x1, x2, ..., xN ∈ [ 0, 1]s についても,




この等式は次の意味で, ぎりぎりの情報を与えています.

どんな x1, x2, ..., xN ∈ [ 0, 1]s と, どんな ε > 0 に対しても適当な関数 f が存在して

V(f)=1だが




したがって, 数値積分の誤差は, Star-discrepancy D*N(x1,…, xN) に大きく依存します.


主な予想

次の二つが成立すると研究者により予想されています. 以下, 記号 ln で自然対数を表します.

予想1. 次元 sだけによる定数 cs があって, どんな x1, x2, ..., xN ∈ [ 0, 1)s についても,




予想2. 次元 s だけによる定数 c's があって, どんな x1, x2, ..., xN ∈ [ 0, 1)s についても,


これらの予想は同等です.

これらの予想は, 2以下の整数 s では W.M.Schmidt により証明されましたが, 3以上の整数 sでは解決されてません.



超一様分布列

定義. 超一様分布列(low-discrepancy sequence, 昔は準乱数列といった)とは, s 次元単位立方体内の無限点列であり, それをx1, x2, ..., と表すとき, 適当な C が存在して,
全ての N>1 に対して先頭のN点が



を満たすものである.

例えば, van der Corput 列は s=1 の時の超一様分布列です. s が一般のとき超一様分布列として
Faure, Halton, Sobol, Niederreiter によるものがあり, それらの一般論は Niederreiter による (t,m,s)-列などがある. Halton列が実際にそうであることの証明はここ (dviファイル, pdfファイ ル).


予想 2にあるように, これらの超一様分布列は最も良い可能なオーダーの収束性能があると信じられています.


超一様分布列の応用


参考文献

  1. 手塚集, 「超一様分布列の数理」, 岩波書店「統計科学のフロンティア」シリーズの第11巻「計算統計I」. 本館学閲DT1/089
  2. ニュートン・コーツ型数値積分」, 赤間陽二
  3. 楠岡成雄「積分を計算する(整数論の数値計算への応用)」, 東京大学 数学公開講座「数理科学の広がり」, 2003(動画)
  4. Harald Niederreiter, Random Number Generation and Quasi-Monte Carlo Methods (C B M S - N S F Regional Conference Series in Applied Mathematics) 2007/10/11(木)1300からこの本の輪読を行います(部 外者の参加も歓迎します.数 学棟412号室に集合).




演習5.
適当な定積分を準モンテカルロ法で求め, 収束の様子を調べよ.




擬似乱数列   行列の掃き出し法のアルゴリズム
と応用