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

モンテカルロ法とは

乱数を用いて何らかの値を見積もる方法をモンテカルロ法と言います。

乱数を用いるため「解を正しく出力することもあれば，大きく外れることもある」というランダムなアルゴリズムになります。

そのため「どれくらいの確率でどのくらいの精度で計算できるのか」という精度の評価が重要です。そこで確率論が活躍します。

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

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

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

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

精度の評価

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

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

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

例えば，$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$ 回くらい必要になります。

誤差 $1$ ％におさえるために10万個も点を打つなんてやってられないですね。

※Chernoffの不等式については，Chernoff bounds, and some applicationsが詳しいです。ここでは，上記の文献の Corollary 5 を使いました。

◎確率・統計分野の記事一覧