1946 - Ulam 蒙地卡羅#

案件摘要#

1946 年，Stanisław Ulam 在 Los Alamos 療養時玩接龍牌局，突然想到：與其組合分析算出贏牌機率，不如實際玩一百局數一數。他立刻意識到這招能解決中子鏈鎖反應的問題——中子散射路徑的組合複雜度根本無法解析計算，但可以用電腦模擬幾千條隨機路徑統計其行為。蒙地卡羅方法就此誕生，是人類第一次把「擲骰子」變成嚴肅的科學計算工具。

前因 -- 為什麼會有這個案子#

曼哈頓計畫的中子輸運問題：一個中子在裂變材料中隨機散射、吸收、引發裂變，問臨界質量是多少。解析方法（積分方程）在多維、多階段下完全失效——組合爆炸。而當時 ENIAC 剛問世，Ulam 看到的是：電腦可以快速擲骰子。這正好接上 Buffon 擲針（見 1777-Buffon針實驗.md）的老思想，但第一次有了真正的計算引擎。

線索與推理 -- 數學式、程式、理論#

核心思想：用平均值估計積分#

要計算積分：

\[ I = \int_\Omega f(x)\, dx \]

確定性方法（梯形法）在 \(d\) 維下誤差 \(O(N^{-2/d})\) ——維度越高越慘。蒙地卡羅改為：從 \(\Omega\) 均勻取樣 \(x_1, \dots, x_N\) ，計算

\[ \hat{I}_N = \frac{|\Omega|}{N} \sum_{i=1}^N f(x_i) \]

驚人的事實：誤差 \(O(1/\sqrt{N})\) ，與維度無關！

\[ \mathrm{Var}(\hat{I}_N) = \frac{|\Omega|^2 \mathrm{Var}(f)}{N} \implies \text{誤差} \sim \frac{|\Omega|\sigma_f}{\sqrt{N}} \]

這就是蒙地卡羅擊敗解析方法的原因：高維問題（如中子散射的相空間）只有它能算。

期望值估計的正確性#

由大數法則： \(\hat{I}_N \xrightarrow{a.s.} I\) 。由中央極限定理：

\[ \hat{I}_N \approx \mathcal{N}\left(I, \frac{\sigma_f^2}{N}\right) \]

要 99% 置信度誤差小於 \(\epsilon\) ，需要 \(N \approx (2.58 \sigma_f / \epsilon)^2\) 次——平方換精度，但維度免費。

程式碼：蒙地卡羅估計 π 與高維積分#

import random, math

def mc_pi(n=1000000):
    """單位圓面積/正方形面積 = π/4"""
    inside = sum(1 for _ in range(n)
                 if (x:=random.random())**2 + (y:=random.random())**2 <= 1)
    return 4 * inside / n

random.seed(42)
print(mc_pi())   # 約 3.1418

def mc_integral(f, a, b, n=1000000):
    """一維蒙地卡羅積分"""
    return (b - a) * sum(f(random.uniform(a, b)) for _ in range(n)) / n

print(mc_integral(math.exp, 0, 1))   # ≈ 1.71828 = e - 1

# 高維的勝利：10 維球體積（解析值極難）
def mc_ball_10d(n=1000000):
    dim = 10
    inside = 0
    for _ in range(n):
        p = [random.uniform(-1, 1) for _ in range(dim)]
        if sum(v*v for v in p) <= 1:
            inside += 1
    return (2**dim) * inside / n   # ≈ 2.55（解析值 V10 = π^5/5! ≈ 2.5502）

中子輸運的模擬#

每個中子是一條隨機路徑：出生 → 直行（距離服從指數分佈）→ 碰撞 → 散射（方向隨機）或吸收或裂變（分支）。模擬 \(N\) 條路徑，統計「增殖因子」 \(k\) ：

\[ k = \frac{\text{下一代中子數}}{\text{這一代中子數}} \]

\(k > 1\) 超臨界（爆炸）， \(k < 1\) 次臨界（熄滅）。原子彈與核反應爐的設計，靠的是幾千次擲骰子。

命名的由來#

Metropolis 建議以摩納哥賭場「蒙地卡羅」命名——Ulam 的叔叔會向親戚借錢去那裡賭博，「因為數學上總有機會贏」。這個名字精確捕捉了方法的本質：用受控的賭博換取確定的統計答案。

偵探筆記：接龍牌局 → 中子散射 → 通用積分估計——Ulam 的推理是一次漂亮的「由特殊到一般」抽象：任何「太複雜算不清、但能模擬」的系統，都可以用隨機樣本統計。

結案 -- 後果與影響#

核工程：至今所有核反應爐與核武設計都用蒙地卡羅輸運模擬（MCNP 等軟體）。
計算物理/化學：統計力學系統模擬（Ising 模型、量子蒙地卡羅）。
MCMC 革命：Metropolis (1953) 將其一般化到任意分佈取樣（見 1953-MetropolisHastings演算法.md），成為貝葉斯統計的引擎。
隨機算法學科：1970–80 年代 Rabin、Karp 等人把「擲骰子」帶入演算法設計（質數檢驗、字串匹配、圖算法）。
金融工程：選擇權定價（Black–Scholes 的蒙地卡羅實現）。
圖形學：路徑追蹤（path tracing）光線渲染本質是蒙地卡羅積分。

關鍵人物與文獻#

Stanisław Ulam（1909–1984）：Adventures of a Mathematician（自傳，記述接龍靈感）
Nicholas Metropolis（1915–1999）：命名者、Metropolis 演算法
John von Neumann：設計第一版蒙地卡羅程式（ENIAC, 1947–48）
Metropolis & Ulam：The Monte Carlo Method (1949, J. Amer. Statist. Assoc.)
交叉參照：1777-Buffon針實驗.md、1905-布朗運動.md、1953-MetropolisHastings演算法.md