Monte Carlo 収束速度比較

同じ点数でランダムな点列と Halton 数列を使って $\\pi$ を推定します。低差異数列は、ランダムサンプリングの平均的な振る舞いと比べて、より速く収束します。

問題設定

単位正方形 $[0,1]^2$ 内に一様に点を打ち、単位円内に入る点の割合から $\\pi$ を推定します。

\\pi \\approx 4 \\times \\frac{\\text{単位円内の点数}}{\\text{全点数}}

どちらも 1024 点を使った 1 回の推定です。ランダムはシードごとに揺れますが、Halton 数列は決定論的なので何度実行しても同じ値になります。

点列	推定値	誤差
ランダム	3.06250	0.07909
Halton	3.14844	0.00684

点そのものの分布と、格子で測った一様性の指標は Halton Sequence を参照してください。

10 回50 回100 回

グラフは 50 回のランダム試行の平均（実線）と標準偏差の範囲（帯）を示しています。個別のランダム試行では Halton より良い結果になることもありますが、平均的には Halton の誤差が小さくなります。