モンテカルロ法と円周率の近似計算

レベル: ◎ 大学数学その2

更新日時 2021/03/07

モンテカルロ法の具体例として，円周率の近似値を計算する方法，およびその精度について考察します。

モンテカルロ法とは

乱数を用いて何らかの値を見積もる方法をモンテカルロ法と言います。
乱数を用いるため「解を正しく出力することもあれば，大きく外れることもある」というランダムなアルゴリズムになります。
そのため「どれくらいの確率でどのくらいの精度で計算できるのか」という精度の評価が重要です。そこで確率論が活躍します。

円周率の近似値を計算する方法

モンテカルロ法の具体例として有名なのが円周率の近似値を計算するアルゴリズムです。

モンテカルロ法

$1\times 1$ の正方形内にランダムに点を打つ（→注）
原点（左下の頂点）から距離が $1$ 以下なら $1$ ポイント， $1$ より大きいなら $0$ ポイント追加
以上の操作を $N$ 回繰り返す，総獲得ポイントを $X$ とするとき， $\dfrac{4X}{N}$ が円周率の近似値になる

注： $[0,1]$ 上の一様分布に独立に従う二つの乱数 $(U_1,U_2)$ を生成してこれを座標とすれば正方形内にランダムな点が打てます。

図の場合， $\dfrac{4\cdot 8}{11}=\dfrac{32}{11}\fallingdotseq 2.91$ が $\pi$ の近似値として得られます。

大雑把な説明

各試行で $1$ ポイント獲得する確率は $\dfrac{\pi}{4}$

試行回数を増やすと「当たった割合」は $\dfrac{\pi}{4}$ に近づく（→大数の法則）

つまり， $\dfrac{X}{N}\fallingdotseq \dfrac{\pi}{4}$ となるので $\dfrac{4X}{N}$ を $\pi$ の近似値とすればよい。

精度の評価

試行回数 $N$ を大きくすれば，円周率の近似の精度が上がりそうです。以下では数学を使ってもう少し定量的に評価します。

目標は試行回数を◯◯回くらいにすれば，十分高い確率で，円周率として見積もった値の誤差が△△以下であるという主張を得ることです。

Chernoffの不等式という飛び道具を使って解析します！　 $e^x$ を $\exp x$ と書きます。

導出

Chernoffの不等式(※)より，

$P[|X-E[X]|\geq \varepsilon E[X]]\leq 2\exp\left(-\frac{E[X]\varepsilon^2}{3}\right)$

（期待値より大きく外れる確率は十分小さいという意味）

つまり，

$1-2\exp\left(-\frac{E[X]\varepsilon^2}{3}\right)=$ $1-2\exp\left(-\frac{\pi N\varepsilon^2}{12}\right)$ 以上の確率で，

$|X-E[X]| <\varepsilon E[X]$

$(1-\varepsilon)E[X] <X < (1+\varepsilon)E[X]$

$\dfrac{\pi N(1-\varepsilon)}{4} <X < \dfrac{\pi N(1+\varepsilon)}{4}$

$\pi(1-\varepsilon) <\dfrac{4X}{N} < \pi(1+\varepsilon)$

例えば， $90$ ％以上の確率で，誤差約 $1$ ％（ $\varepsilon=0.01$ ）以内にしたい場合， $1-2\exp\left(-\frac{\pi N\cdot 0.01^2}{12}\right)\geq 0.9$ ならよいので， $N\fallingdotseq 1.1\times 10^5$ 回くらい必要になります。