確率と統計 · モンテカルロ法

モンテカルロ法

モンテカルロ法は無作為抽出によって数値を推定する方法です。単位正方形にN個の点を独立に一様に打つと、領域に入った点の割合からその面積を推定でき、標準誤差は1/√Nに比例します。点を打って、πの推定値が落ち着く様子と不確かさの変化を観察してください。

図で見るモンテカルロ法

モンテカルロ法は無作為抽出によってある一定の値を推定します。ここで求めたいのは面積です。単位正方形に一様ランダムに打ったNN個の点のうちHH個が領域に入れば、H/NH/Nがその面積aaの推定値になります。四分円の面積はπ/4\pi/4なので、4H/N4H/Nからπ\piを推定できます。y=e−x2y = e^{-x^2}の下の領域なら、初等関数で表せる原始関数がない積分も同じ数え方で推定できます。下段のグラフはNNが100万まで増えるときの推定値と、約95%の試行で推定値が入ると見込まれる範囲を示します。

なぜ割合で面積を推定できるのか

面積1の正方形で点を一様に選ぶと、ある領域に入る確率はその面積に等しくなります。各点は同じ確率の独立な試行なので、大数の法則により命中した点の割合はaaに近づきます。点が領域内かどうか判定できれば、形は問いません。

どのくらい正確か

命中数は二項分布に従うので、命中割合H/NH/Nの標準偏差はa(1−a)/N\sqrt{a(1-a)/N}です。典型的な誤差は1/N1/\sqrt{N}に比例して小さくなります。点数を10倍にしても誤差は約10≈3.16\sqrt{10} \approx 3.16分の1で、10分の1にするには約100倍の点が必要です。100万点でもπには約±0.003の不確かさが残ります。この幅を見積もるのに真の面積は要りません。aaを観測割合p^=H/N\hat p = H/Nに置き換えると誤差幅±1.96p^(1−p^)/N\pm 1.96\sqrt{\hat p(1-\hat p)/N}が得られ、近似的な95%信頼区間を作れます。ここでは命中と外れがそれぞれ10点以上になってから使います。NNを固定して実験を何度も繰り返すと、およそ20回に1回は区間が真の値を外します。下段の青い帯はNNごとに真の値の周囲に描いた範囲で、軌跡全体が収まる必要はありません。1回の実験では、点を増やすとかえって推定値が真の値から離れることもあります。着実に小さくなるのは誤差の幅です。

どんなときに有利か

滑らかな1変数関数なら、同じ評価回数ではシンプソン則(数値積分参照)などの決定論的な方法の方がはるかに正確です。モンテカルロ法は収束率1/N1/\sqrt{N}の指数が次元に依存しないのが強みです。一方、1辺にmm個の点を置く格子は、dd次元でmdm^d個の点を必要とします。そのため、高次元ではモンテカルロ法が有利になることがあります。小さな領域は苦手です。面積に対する相対標準誤差は(1−a)/(aN)\sqrt{(1-a)/(aN)}なので、正方形の100分の1の領域を同じ相対精度で測るには、はるかに多くの点が必要です。

観察のポイント

  • ランダムな点は等間隔には並びません。数百点なら集まりや空白ができるのは自然です。
  • 点は番号付きのシードを使う疑似乱数生成器で作ります。共有リンクを開くと同じ点が再現され、100万点に達してから「点を打つ」を押すと、次のシードで最初から始まります。

関連