誤解を恐れずに言えば，Quasi-Monte Carlo 法は2つの矛盾した目標を達成しようとしている．
- 分布の不規則性(irregularity of distribution)を最小化する．
- aliasing 問題を避けるため regular な uniform sampling はしない．
分布の不規則性を最小化するには，不規則でないもの，つまり regular なuniform sampling を行えば良い．しかし，regular な uniform sampling ではaliasing の影響を受けてしまい，Monte-Carlo 法の利点がなくなってしまう．
この discrepancy は，irregularity of distribution を数値化する方法である．これはどれだけの integration error が起こりそうかを示す数値である．
Star discrepancy D_N^* は，discrepancy の一種で，これは原点を含む様々な形の box をサンプルした場合に，それらの box の area を間違えてしまう最大の値である．
1 次元の場合には，箱は線になるので，原点を含む様々な長さの線をサンプルすることに相当する．N 点でサンプルすると，Uniform に distribute しても1/(2N) 以下はサンプルできない．この場合には Sampling theory そのものなので問題はないが，高次元(s次元)になるとO((log(N)^s) /N) という話がある．
なぜ O((log(N)^s) /N) なのかは残念ながら私にはよくわからない．1 次元の場合には適用できないことも謎だ．どうやらややこしい証明があるということである．しかし，どんな分布になるのかは plot してみると図1 のようになっている．サンプル数が少ない場合や，高次元の場合にはエラーが大きいので傾向はわかるが，それだけしかわからないのは残念である．これは log(N)^s と N の増大の比だから，明らかという人もいらっしゃることであろうが，一度見てみたかった．
これを Plot する program はここである．matlab/octave という言語で書いてある．
-----
%
% visualize star discrepancy
% Octave code: 2010 (C) Shitohichi Umaya
%
x = [10000:100:1000000];
s = 2
y1 = power(log(x), s)./x;
s = 3
y2 = power(log(x), s)./x;
plot(x,y1,"1;(log N)^s/N, s=2;", x,y2,"3;(log N)^s/N, s=3;")
-----
謝辞
Discrepancy に関する質問に答えて下さった Alexander K. に感謝する．