跳轉到

10.2 蒙地卡羅方法（1946）#

本章導言#

1946 年冬，Stanislaw Ulam（烏拉姆，1909–1984） 玩接龍牌局時想到：與其組合分析勝率，不如玩一百局數一數。這個念頭在 John von Neumann（馮紐曼，1903–1957） 的推動下成為「以隨機抽樣做數值計算」的方法，於 Los Alamos 實驗室誕生，以摩納哥賭城命名（Ulam 叔叔常在蒙地卡羅借錢賭博）。本節講述蒙地卡羅的原理、三大應用戰場與計算機時代的位置。

誕生：氫彈與 ENIAC#

Ulam–von Neumann 1946 年的構想服務於中子輸運問題（原子彈內中子的隨機行走——6.1 節的物理化身）：追蹤萬千條中子軌道的「碰撞—散射—吸收」直至終結，統計輸出。1948 年 Nicholas Metropolis 與 von Neumann 以 ENIAC 完成首批大規模模擬。方法的理論根基：

  • 大數法則（5.1 節）： \(\hat{I}_M = \frac{1}{M} \sum_{i=1}^{M} h(X_i) \xrightarrow{P} \mathbb{E}[h(X)] = I\) 。
  • 中心極限定理（5.2 節）：誤差 \(\approx \frac{\sigma_h}{\sqrt{M}}\) ——收斂速率 \(M^{-1/2}\) 與維數無關！這是蒙地卡羅對確定性數值方法的殺手級優勢：積分維數 \(d\) 越高，格點法（ \(N^d\) 點）越崩潰，蒙地卡羅照常工作。

「以賭城的隨機性求解科學的確定性」——方法名的戲謔精確地道出其本質：隨機性是計算資源。

抽樣技術的演進#

原始蒙地卡羅（crude MC）之後，方差削減技術使效率倍增：

  • 反函數法（2.1 節場景三）： \(F^{-1}(U)\) 抽樣任意分布。
  • 重要抽樣（importance sampling）：以偏向難抽區域的分布 \(g\) 抽樣，權重 \(\frac{f}{g}\) 修正——稀疏事件（如 \(10^{-9}\) 機率的故障）的蒙地卡羅必備。
  • 控制變量與對偶變量：以期望已知的輔助量吸收波動。
  • Metropolis–Hastings（1953/1970）與 Gibbs（1984）：MCMC——以馬可夫鏈（6.2 節）採樣任意後驗，9.3 節貝氏復興的引擎。
  • 準蒙地卡羅（QMC）：以低差異序列（Sobol 1967）替代偽隨機數，誤差從 \(M^{-1/2}\) 改善到近 \(M^{-1}\) （光滑被積函數下）——金融工程的高維定價標配。

三大應用戰場#

戰場一：物理。中子/粒子輸運（誕生地）、統計力學的 Metropolis 採樣（1953：Boltzmann 分布的採樣器，也是計算物理與 MCMC 的共同祖先）、量子蒙地卡羅（電子結構計算）。戰場二：貝氏統計。MCMC 後驗採樣（9.3 節）使所有複雜模型可算——蒙地卡羅在此的化身是「統計推論的計算基礎設施」。戰場三：金融工程。路徑依賴衍生品（亞式選擇權）定價 = Feynman–Kac 期望的模擬（7.3 節）；風險值（VaR）的蒙地卡羅在 1990 年代隨 Basel 協議普及。

一個具體例題#

例題 10.2.1：以蒙地卡羅估計 \(I = \int_0^1 e^{-x^2} dx\) （無初等原函數）。(a) 設計基本蒙地卡羅估計量並給出誤差公式；(b) 以對偶變量改進；(c) 估算達到誤差 \(10^{-4}\) 所需的樣本量；(d) 與數值積分（Simpson）比較。

解：

(a) 寫 \(I = \mathbb{E}[e^{-U^2}]\) ， \(U \sim U(0,1)\) 。估計量：

\[ \hat{I}_M = \frac{1}{M} \sum_{i=1}^M e^{-U_i^2}, \qquad \text{誤差標準差} \approx \frac{\sigma}{\sqrt{M}}, \quad \sigma^2 = \operatorname{Var}(e^{-U^2}). \]

（理論值 \(I = \frac{\sqrt{\pi}}{2}\operatorname{erf}(1) \approx 0.7468\) 。）被積函數的範圍 \([e^{-1}, 1]\) ，粗估 \(\sigma^2 \approx 0.02\) 。

(b) 對偶變量： \(g(u) = \frac{e^{-u^2} + e^{-(1-u)^2}}{2}\) （ \(U\) 與 \(1-U\) 同分布，兩者負相關，平均後方差銳減）。 \(g\) 的範圍縮為 \([e^{-0.75}, 0.5(1 + e^{-1})]\) ，方差約降一個量級（ \(\sigma_g^2 \approx 0.002\) ）。

(c) 基本 MC： \(M = \frac{\sigma^2}{\varepsilon^2} \approx \frac{0.02}{10^{-8}} = 2 \times 10^6\) 次；對偶版： \(M \approx \frac{0.002}{10^{-8}} = 2 \times 10^5\) 次——十倍效率。方差削減的價值直接換算成計算成本。

(d) 一維光滑積分：Simpson 法誤差 \(O(h^4)\) ， \(h = 10^{-3}\) （千分點）即達 \(10^{-12}\) 級精度——數值積分碾壓蒙地卡羅。但改到 10 維：格點法需 \(1000^{10} = 10^{30}\) 點（宇宙原子數的量級！），蒙地卡羅仍是 \(10^8\) 點。結論：維數是方法選擇的裁判——低維用確定性方法、高維用隨機方法（7.3 節場景五的「誤差結構匹配問題結構」的具體化）。

歷史啟示#

  • 隨機性作為演算法：蒙地卡羅是「用隨機性買計算複雜度」的第一例——此後（隨機化演算法、隨機梯度下降）成為計算科學的主流策略。
  • 維數無關性的解放： \(M^{-1/2}\) 與 \(d\) 無關，使高維積分（貝氏後驗、金融組合、量子系統）從不可能變成日常——「維度詛咒」被隨機性豁免。
  • 三場戰爭一個方法：核武器（1946）、統計計算（1984–90）、金融工程（1990s）——同一數學的三大用戶群，相互餵養（方差技術多來自金融需求）。
  • 娛樂孕育科學：接龍牌局的直覺（Ulam）、賭城的命名——蒙地卡羅證明「機率論回到賭桌」的完整循環：1654 年賭桌產生機率論，1946 年機率論以賭城之名回饋科學。

與其他章節及領域的關聯#

  • 5.1、5.2 節：大數法則與 CLT 是蒙地卡羅的收斂與誤差理論。
  • 2.1 節：反函數抽樣、分布變換。
  • 6.1、6.2 節：隨機漫步（粒子輸運）與馬可夫鏈（MCMC）。
  • 7.3 節：Feynman–Kac 使 PDE 可蒙地卡羅化。
  • 9.3 節：MCMC 之於貝氏復興。
  • 10.1 節：bootstrap（Efron 1979）是蒙地卡羅的統計推論版——以重抽樣逼近抽樣分布。
  • 計算機科學：隨機化演算法（Miller–Rabin 質數檢定 1976、RSN）、粒子濾波（4.3 節場景二）、隨機梯度下降（深度學習的引擎本質是「隨機化的優化」）。
  • 核工程與輻射防護：MCNP 等蒙地卡羅程式至今是核安全分析的產業標準。

練習#

  1. 以 \(U \sim U(0,1)\) 估計 \(\pi\) ：設計「單位正方形內隨機點落入四分之一圓」的估計量，計算其方差與達到 3 位小數所需的 \(M\) 。
  2. 重做例題 10.2.1(b)：驗證 \(g(u)\) 的方差小於 \(e^{-u^2}\) 的方差（計算 \(\operatorname{Var}(g(U))\) 與 \(\operatorname{Var}(e^{-U^2})\) ）。
  3. 重要抽樣：以 \(g(x) = 2x\) （ \(0 \le x \le 1\) ）抽樣估計 \(I = \int_0^1 \sqrt{x}\, dx = \frac{2}{3}\) ，證明估計量 \(\frac{1}{M}\sum \frac{\sqrt{U_i}}{2U_i} = \frac{1}{M}\sum \frac{1}{2\sqrt{U_i}}\) 無偏，並比較與均勻抽樣的方差。
  4. 說明為什麼 MCMC 的樣本是「相關的」，誤差估計因此不能直接用 \(\frac{\sigma}{\sqrt{M}}\) ，並描述「有效樣本量（ESS）」的修正思路。
  5. 思考題：Ulam 的接龍直覺是「實驗代替分析」。請以一個現代場景（如排隊系統、保險組合）說明何時模擬優於解析、何時解析優於模擬，並討論「模擬讓人停止思考解析解」的風險。

進階研讀：隨機計算的五個深化場景#

場景一：bootstrap——蒙地卡羅的統計化身。Efron（1979）的 bootstrap：以經驗分布（2.1 節場景五）為母體重抽樣，逼近任何統計量的抽樣分布——複雜估計量（中位數的區間、迴歸係數）的信賴區間從此無需樞紐量。bootstrap 理論（Bickel–Freedman 1981 的漸近有效性）使其成為「計算替代數學」的典範，也是現代數據科學（重抽樣驗證）的基礎。

場景二：粒子濾波與即時推斷。Kalman 濾波（4.3 節場景二）只處理線性高斯；粒子濾波（Gordon–Salmond–Smith 1993）以加權粒子群近似任意後驗、逐步重採樣——導航、目標追蹤、機器人定位（SLAM）的實時貝氏推斷。蒙地卡羅從離線計算走進了閉環控制。

場景三：蒙地卡羅樹搜尋（MCTS）與 AlphaGo。把隨機模擬用於搜尋：MCTS（2006，Coulom、Kocsis–Szepesvári）以「隨機對局 + 統計聚合 + UCB 平衡探索/利用」評估棋步。AlphaGo（2016）以 MCTS + 深度網路擊敗李世石——1946 年的隨機抽樣思想 + 2010 年代的深度學習 = 棋類革命。Ulam 的接龍與圍棋之間隔著七十年的方差削減史。

場景四：準蒙地卡羅與高維積分的再征服。QMC 以 Sobol/Halton 低差異序列替代偽隨機數；Koksma–Hlawka 不等式（1959）給誤差界 \(O\left(\frac{(\log M)^d}{M}\right)\) ——雖有 \(d\) 因子，光滑高維問題上實際表現常勝 MC。金融的希臘字母估計、VaR 的敏感度計算大量採用 QMC + 重要抽樣——「隨機與確定性的中間路線」。

場景五：蒙地卡羅作為認識論工具。蒙地卡羅改變了科學的驗證方式：以模擬檢驗解析理論（如 CLT 的收斂速率實驗、6.1 篝反正弦律的教學驗證）、以置換檢驗繞過分布假設（8.3 節場景二）、以 MCMC探索不可解析的後驗。「跑一次看看」從工程口號變成科學方法的一部分——但其認識論地位（模擬是證據嗎？）仍在哲學討論中（Winsberg 2010 的模擬科學哲學）。

名詞速查表（本節出現的核心術語）#

  • 蒙地卡羅估計： \(\hat{I}_M = \frac{1}{M}\sum h(X_i)\) ，誤差 \(\sim \frac{\sigma}{\sqrt{M}}\) 。
  • 維數無關性：收斂速率與積分維數無關（高維的核心優勢）。
  • 重要抽樣：偏向性抽樣 + 權重修正，稀疏事件的解法。
  • 對偶/控制變量：負相關或已知期望的方差削減。
  • MCMC：馬可夫鏈平穩分布採樣（MH、Gibbs、HMC）。
  • 準蒙地卡羅（QMC）：低差異序列的確定性替代。
  • bootstrap：經驗分布重抽樣的統計推論（Efron 1979）。
  • 粒子濾波：加權粒子的即時貝氏推斷。
  • MCTS：蒙地卡羅樹搜尋，AlphaGo 的搜尋引擎。
  • ESS：有效樣本量，相關樣本的誤差修正。

年表速查（本節涉及的關鍵年份）#

  • 1946：Ulam–von Neumann 構想；命名蒙地卡羅。
  • 1948：ENIAC 首批大規模模擬。
  • 1953：Metropolis 演算法（統計力學採樣）。
  • 1959：Koksma–Hlawka 不等式（QMC 理論）。
  • 1967：Sobol 序列。
  • 1970：Hastings 推廣 MCMC。
  • 1976：Miller–Rabin 隨機化質數檢定。
  • 1979：Efron bootstrap。
  • 1984：Geman–Geman Gibbs 抽樣。
  • 1990：Gelfand–Smith 貝氏計算引爆。
  • 1993：粒子濾波。
  • 2006：MCTS 演算法。
  • 2016：AlphaGo（MCTS + 深度學習）。

深化問答三則#

問：為什麼蒙地卡羅的 \(M^{-1/2}\) 「慢」卻統治了高維計算？ 答：因為競爭者更慘：確定性網格在 \(d\) 維需 \(N^d\) 點（指數爆炸），擬蒙地卡羅的 \(M^{-1/2}\) 是多項式。慢而穩定勝過快而崩潰——計算複雜度的比較總是「相對於維數」的。例題 10.2.1(d) 的一維比較提醒我們：蒙地卡羅從不謀求「最高精度」，只謀求「任意維度下可接受精度」——它的成功是生態位的成功。

問：MCMC 的樣本「相關」為什麼是問題？ 答：大數法則與 CLT 的古典形式假設獨立（5.1 篝）；相關樣本的方差估計必須以自協方差修正（ESS = 總樣本量除以積分自相關時間）。若鏈卡在局部模態，ESS 可以低到「看起來 10 萬個樣本、實際 20 個」——診斷（6.2 篝譜隙、9.3 篝場景五）因此是 MCMC 實務的生死線。這是「馬可夫鏈理論（1906）→ 貝氏計算（1990）→ 診斷學（2000s）」的最後一環。

問：隨機化演算法的哲學：把正確性交給擲骰子合法嗎？ 答：合法且深刻。蒙地卡羅把「確定性錯誤（偏差）」換成「隨機性錯誤（方差）」，後者可以以機率 \(1-\delta\) 控制在 \(\varepsilon\) 內（增加 \(M\) ），且失敗可重試、錯誤不累積。Miller–Rabin 以「多擲幾次」達到任何所需的錯誤率——密碼學接受它正因其錯誤可量化、可壓低、可獨立重試。這是機率論對「可靠性工程」的全新貢獻：可靠性不必來自確定性，可以來自可管理的隨機性——這句話也可以作為全書的註腳。

（本節完）