乱数とモンテカルロ法
乱数とは, でたらめな数を次々に作る方法、またはそうして生成された数列を指す.
物理乱数：物理現象を利用した乱数
議事乱数：漸化式などに基づく乱数
モンテカルロ法
$\pi$ を求める問題などで用いられる.
例1
$N$ 組の乱数中で $U^2 + V^2 < 1$ となる乱数の組の個数 $M$ とすると, $\pi$ は $\hat{\pi} = \frac {4M} {N}$ となる. $M$ は二項分布 $Bin(N, \frac {\pi} {4})$ に従うので,
$$
V[M] = N \frac {\pi} {4} (1 - \frac {\pi} {4})
$$
より, $\hat{\pi} = \frac {4M} {N}$ の標準偏差は
\begin{align}
SD(\frac {4M} {N}) &= \sqrt{V(\frac {4M} {N})} \\
&= \sqrt{\frac {16} {N^2} V(M)} \\
&= \sqrt{\frac {16} {N^2} N \frac {\pi} {4} (1 - \frac {\pi} {4})} \\
&= \sqrt{\frac {\pi(4 - \pi)} {N}}
\end{align}
したがって, $SD(\pi) = 0.01$ とすると,
\begin{align}
\sqrt{\frac {\pi(4 - \pi)} {N}} &= 0.01 \\
\frac {\pi(4 - \pi)} {N} &= 0.01^2 \\
N &= \frac {\pi(4 - \pi)} {0.01^2}
\end{align}
乱数生成・逆関数法
あらゆる確率分布に従う乱数生成は, 一様分布からの乱数, つまり一様乱数の発生に基づいて行われる. 区間 $(0,1)$ の一様分布に従う確率変数を $U$ とする.
1変量の確率変数 $X$ が確率密度関数 $p_X(x)$ と分布関数 $F_X(x)$ と持つとする. もし, $F_X(x)$ の逆関数 $F_X^{-1}(u)$ がように得られる場合, 次の逆関数法と呼ばれる方法で $X$ の乱数が生成できる.
- $U(0,1)$ から一様乱数 $u$ を 1 つ得る
- $x = F_X^{-1}(u)$ とする.
逆関数法で $X$ の乱数が生成できることは, 以下が成り立つためである.
$$
P(F_X^{-1}(U) < x) = P(U < F_X(x))) = F_X(x)
$$
最後の指揮変形は, $U$ が一様分布に従う確率変数のため $P(U<u)=u$ より成り立つ.
つまり, $F_X^{-1}(U)$ に従う確率変数の累積分布関数が, $F_X(x)$ の分布関数と等しいことを示している.
例2
$X$ の累積分布関数は
$$
F_X(x) = \int_{0}^{x} 2e^{-2x} dx = 1 - e^{-2x}
$$
であるので,
$$
F_X^{-1}(u) = - \frac {1} {2} \log (1 - u)
$$
である. また, $U \sim U(0,1)$ のとき $1-U \sim U(0,1)$ であるから, 以下のように逆関数法により $x$ の乱数が生成できる.
- $U(0,1)$ から一様乱数 $u$ を 1 つ得る
- $x = - \frac {1} {2} \log (1 - u)$ とする.
モンテカルロ積分
関数 $g(x)$ の区間 $(0,1)$ 上の積分を推定する問題を考える.
$$
\theta = \int_0^1 g(x)dx
$$
確率変数 $X$ が $U(0,1)$ に従うとき,
$$
\theta = \int_0^1 g(x) \cdot 1dx = E[g(X)]
$$
したがって, $X_1, ..., X_m$ が$U(0,1)$ からの無作為標本とするとき, 対数の弱法則より,
$$
\hat{\theta} = \frac {1} {m} \sum_{i=1}^{m} g(X_i)
$$
このように, $m$ 個の $U(0,1)$ 上の一様乱数を発生させ, $\frac {1} {m} \sum_{i=1}^{m} g(X_i)$ で推定する方法を単純モンテカルロ積分という.
例4
一様乱数として $U(2,5)$ を使うので,
$$
I = \int_2^5 (5-2) e^{-x} \frac {1} {5-2} dx = \int_2^5 3e^{-x} \frac {1} {3} dx
$$
よって, $g(x) = 3e^{-x}$ とおくことで, 単純モンテカルロ法は次のとおりである.
- $U(2,5)$ から独立な一様乱数を $m$ 個とる
- $\hat{I} = \frac {1} {m} \sum_{i=1}^{m} 3e^{-x_i}$ とする.