モンテカルロ法の基礎知識

乱数とはある有限の範囲の数の集合から無作為に（ランダムに）選んだ数である。例えばコインを投げて表がでた場合に０，裏の場合には１と決定する目は乱数である。

乱数は一般にモンテカルロシミュレーションに使われるほか，暗号の分野では暗号鍵に決定や初期ベクトル設定，あるいは零知識証明プロトコルにおけるメッセージ生成に用いられる。無作為に選出された数を利用することにより，シミュレーション結果の信頼性や，暗号プロトコルの安全性を保証しているのである。

しかし，ここで発生させる乱数は上で述べた乱数ではない。C++にあるrand()関数により発生する乱数は次のような方法で発生させている。

$$x_{n+1} = r x_{n} ({\rm mod} N)$$

ここで，$x_{0}$を乱数の種という。

簡単で実用的な乱数は

$$x_{n+1} = 25173x_{n} + 13849 ({\rm mod}65536)$$

により発生させることができる。

ここでは，乱数の応用としてモンテカルロ法を用いた$\pi$の計算を行う。

実際に行うことが困難な実験をコンピュータを用いて模擬的に実験することをシミュレーションという。乱数を用いてシミュレーションを行うことをモンテカルロ法という。このモンテカルロ法を用いてπの計算を行う。

$x$軸と$y$軸， $x = 1,y = 1$の線に囲まれた正方形の中に、ランダムに$N$個の点$P(x,y)$を発生させて、4分の１円の内側に落ちた数を$ｎ$とすると、$N$が大きければ

$$\frac{n}{N} = \frac{４分の１円の面積}{正方形の面積} \approx \frac{\pi}{4}$$

となる。したがって，ランダムに発生した$N$個の乱数$(x,y)$について、 $x^{2} + y^{2} \leq 1$ を満たす数$ｎ$個を数えれば、上式より$\pi$を求めることができる。

乱数の発生　乱数を発生させるにはrand()関数を用いる。

rand()とすると、1からRAND_MAXまでの数をランダムに発生することができる。ただし，このままではいつも同じ数を発生する。そこで，

srand((unsigned) time(NULL));
とすると，時間によって種(seed)がことなり，rand()で発生する数が変わる。time()関数は$<$ctime$>$にある。