2015/07/17

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

分野: 大学の確率・統計  レベル: 大学数学

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

モンテカルロ法とは

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

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

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

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

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

モンテカルロ法

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

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

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

(大雑把な説明)
各試行で $1$ ポイント獲得する確率は $\dfrac{\pi}{4}$
試行回数を増やすと「当たった割合」は $\dfrac{\pi}{4}$ に近づく(→大数の法則
つまり,$\dfrac{X}{N}\simeq \dfrac{\pi}{4}$ となるので $\dfrac{4X}{N}$ を $\pi$ の近似値とすればよい。

精度の評価

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

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

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

(導出)
Chernoffの不等式より,
$P[|X-E[X]|\geq \varepsilon 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 X$
$\dfrac{E[X]}{(1+\varepsilon)} <X <\dfrac{E[X]}{(1-\varepsilon)}$
$\dfrac{\pi N}{4(1+\varepsilon)} <X <\dfrac{\pi N}{4(1-\varepsilon)}$ $\dfrac{\pi}{(1+\varepsilon)} <\dfrac{4X}{N} <\dfrac{\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\simeq 1.1\times 10^5$ 回くらい必要になります。

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

「多分うまくいくけど失敗する可能性もあるよ〜」というアルゴリズムで納得しないといけないのは少し気持ち悪いですが,そのぶん応用範囲が広いです。

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

分野: 大学の確率・統計  レベル: 大学数学