1946 年、ロスアラモスでのフォン・ノイマンの同僚、ポーランドの数学者スタニスワフ・ウラムは脳炎から回復する途中で、一人トランプをして時間をつぶしていた。彼は、一回のゲームが上がる確率はどれくらいだろうと考えた。組合せ論で求めようとすると、絶望的に複雑だった。だが別の方法があった。何百回もやってみて、何回上がったかを数えるのだ。計算機があれば、何千回もできる。

ウラムがこのアイデアをフォン・ノイマンに話すと、彼はすぐにその射程を見てとった。同じ手が、ロスアラモスで二人が取り組んでいた問題、つまり爆弾や原子炉の中の中性子の経路にも使える。中性子は一つ一つ、ランダムにそらされ、吸収され、あるいは増殖する。方程式を解く代わりに、何千もの中性子をシミュレートし、それぞれに何が起こるかをくじで決め、平均をとればよい。ニコラス・メトロポリスは、ウラムのおじが賭けをしに通っていたモンテカルロのカジノにちなんで、この方法に名をつけた。

FERMIAC を手にするスタニスワフ・ウラム。FERMIAC はエンリコ・フェルミの小さな台車で、手でランダムに選んだ中性子の経路を紙の上に描いた。機械仕掛けのモンテカルロである。
FERMIAC を手にするスタニスワフ・ウラム。FERMIAC はエンリコ・フェルミの小さな台車で、手でランダムに選んだ中性子の経路を紙の上に描いた。機械仕掛けのモンテカルロである。Los Alamos National Laboratory · Wikimedia Commons · パブリックドメイン

1948 年、最初のシミュレーションが ENIAC の上で走った。コードの多くを書いたのは、フォン・ノイマンの妻で、歴史上最初期のプログラマーの一人であるクラーラ・ダーン・フォン・ノイマンだった。

ランダムな点で π を計算する

最も簡単な例はこうだ。$x$ と $y$ がともに $0$ と $1$ の間にある点 $(x, y)$ をランダムに選ぶ。点が四分円 $x^2 + y^2 \le 1$ の内側に落ちる確率は面積の比、$\frac{\pi/4}{1} = \frac{\pi}{4}$ である。したがって

$$\pi \approx 4 \times \frac{\text{内側の点の数}}{\text{選んだ点の数}}.$$

推定はゆっくりとしか良くならない。典型的な誤差は $\frac{1}{\sqrt{n}}$ のように減る。小数を一桁増やすには百倍の点が必要だ。$\pi$ を計算するには、はるかに良い方法がある。だが、変数の多い問題、たとえばエネルギー、方向、衝突の種類をともなう三次元の中性子の経路では、モンテカルロ法がしばしば唯一可能な方法になる。その誤差が次元の数によらないからである。

偶然を製造する

計算機は決定論的な機械である。「ランダムな」数はどこから来るのか。1949 年、フォン・ノイマンは平方採中法を提案した。四桁の数をとって二乗し、結果を八桁で書いて、真ん中の四桁をとる。それが次の数である。彼は、これが本当のランダムではないことを十分に承知していた。

算術的な方法で乱数字をつくろうと考える者は、言うまでもなく、罪の状態にある。

— ジョン・フォン・ノイマン「乱数字に関連して用いられる種々の技法」（1951）

この数列はやがて繰り返すか、ゼロに落ちる。だが速く、しかも結果を再現して計算を確かめることができた。今日ははるかに良い生成法が使われているが、フォン・ノイマンの原則は生きている。生成法に求めるのは本当のランダムさではなく、問題が必要とする統計的検定に通ることなのだ。

練習：平方採中法

$1234$ から始めて、平方採中法で数を三つつくれ。

$1234^2 = 1\,522\,756$、八桁で $01522756$ と書くと、真ん中は $5227$。$5227^2 = 27\,321\,529$、真ん中は $3215$。$3215^2 = 10\,336\,225$、真ん中は $3362$。数列は $1234, 5227, 3215, 3362, \ldots$ と始まる。

練習：点はいくつ必要か

$n$ 個の点を使うと、$\pi$ の推定の典型的な誤差はおよそ $\frac{1.6}{\sqrt n}$ である。誤差 $0.01$ には点がいくつ必要か。$0.001$ ではどうか。

$\frac{1.6}{\sqrt n} = 0.01$ から $\sqrt n = 160$、$n = 25\,600$。$0.001$ では $\sqrt n = 1600$、$n = 2\,560\,000$。本文のとおり、小数一桁のために百倍の点が要る。

出典： Nicholas Metropolis、Stanisław Ulam, “The Monte Carlo method”, Journal of the American Statistical Association（1949）· Nicholas Metropolis, “The beginning of the Monte Carlo method”, Los Alamos Science（1987）· John von Neumann, “Various techniques used in connection with random digits”（1951）。

ジョン・フォン・ノイマンの全トピック · ← マージソート：併合して並べる · 公平になる偏ったコイン →

画像クレジット.