1946 年，冯·诺依曼在洛斯阿拉莫斯的同事、波兰数学家斯坦尼斯瓦夫·乌拉姆正在从脑炎中康复，靠玩单人纸牌打发时间。他想知道一局牌能打通的概率是多少。用组合数学去算，复杂得毫无希望。但还有另一个办法：玩上几百局，数一数有多少局打通了。有了计算机，就可以玩上几千局。

乌拉姆把这个想法告诉了冯·诺依曼，后者立刻看出了它的威力：同样的窍门可以用于他们在洛斯阿拉莫斯面对的问题，即中子在炸弹或反应堆中的路径，每个中子都会随机地偏转、被吸收或增殖。不去解方程，而是模拟成千上万个中子，用抽签决定每个中子遇到什么，然后取平均。尼古拉斯·梅特罗波利斯用蒙特卡洛赌场给这个方法命名，乌拉姆的一位叔叔常去那里赌钱。

斯坦尼斯瓦夫·乌拉姆手持 FERMIAC，这是恩里科·费米的一辆小推车，能在纸上画出由人手随机选出的中子路径：一台机械的蒙特卡洛装置。
斯坦尼斯瓦夫·乌拉姆手持 FERMIAC，这是恩里科·费米的一辆小推车，能在纸上画出由人手随机选出的中子路径：一台机械的蒙特卡洛装置。Los Alamos National Laboratory · Wikimedia Commons · 公有领域

1948 年，最早的模拟在 ENIAC 上运行。大部分代码是由冯·诺依曼的妻子克拉拉·丹·冯·诺依曼编写的，她是历史上最早的程序员之一。

用随机点计算 π

最简单的例子：随机抽取点 $(x, y)$，$x$ 和 $y$ 都在 $0$ 和 $1$ 之间。一个点落在四分之一圆 $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）。

约翰·冯·诺依曼的全部主题 · ← 归并排序：靠合并来排序 · 变公平的不公平硬币 →

图片来源.