蒙特卡洛方法

破除误解：蒙特卡洛不是"随机猜测"#

蒙特卡洛方法经常被误解为"乱猜"。实际上，它是用受控的随机采样来估算确定性答案的一类算法。关键词是"受控"——样本的分布、数量和使用方式都是精心设计的，而非随机选择的。

另一个误解：蒙特卡洛只能给出近似答案，不"精确"。但对于许多问题，精确解不可能在有限时间内得到（如高维积分、NP 难问题），而蒙特卡洛能在可接受时间内提供误差可控的估计，这正是它的价值所在。

方法以摩纳哥赌场命名，还容易滑向第三种误解：把它当成一套跟随机对着干、最终能赢的赌术。赌场的优势写在规则里，期望为负；蒙特卡洛估计则要求估计量无偏或偏差可控，方向正好相反。频率能逼近概率，靠的是独立重复与极限定理，不是因为随机站在你这边。把轮盘上的红黑当成“必胜术”的素材，是在用错误的问题调用正确的数学。

核心思想：用频率估算概率，用概率估算积分#

估算 $\pi$ 的经典例子：

在边长为 2 的正方形内，有一个半径为 1 的内切圆。随机均匀撒点：

$$\hat{\pi} = 4 \times \frac{\text{points inside circle}}{\text{total points}}$$

由于圆的面积与正方形面积之比为 $\pi / 4$，当撒点足够多时，频率收敛到概率。

一般化：蒙特卡洛积分

对难以解析计算的积分：

$$I = \int_\Omega f(x) \, dx$$

从 $\Omega$ 上均匀采样 $x_1, x_2, \ldots, x_N$，估计：

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

误差标准差为 $\sigma / \sqrt{N}$，其中 $\sigma$ 是 $f$ 的方差。这意味着精度提高 10 倍需要 100 倍样本——效率似乎不高，但这个收敛速度与维度无关，而传统数值积分的代价随维度指数爆炸（"维度诅咒"）。

用频率估概率，是 大数定律 的工程用法。独立重复一次试验，成功次数除以总次数，会几乎必然收敛到真实概率；正方形里撒点估 $\pi$，不过是把“点落在圆内”当成伯努利试验，圆与正方形的面积比就是那个未知的 $p$。

关键前提有两条：样本真的来自你声称的分布，以及它们近似独立。分布偏了，频率会收敛到错误的数；相依太强，收敛会慢到让人误以为已经够准。所以蒙特卡洛的技术含量不在“多抽几次”，而在证明抽样机制对应着正确的概率空间。

主要变体与技术#

重要性采样（Importance Sampling）：如果函数 $f$ 在某些区域值很大，均匀采样浪费样本。用概率分布 $q(x)$ 来引导采样，集中在重要区域：

$$\hat{I} = \frac{1}{N} \sum_{i=1}^{N} \frac{f(x_i)}{q(x_i)}, \quad x_i \sim q$$

选择好的 $q$ 能将方差降低数个量级。

马尔可夫链蒙特卡洛（MCMC）：当目标分布 $\pi(x)$ 难以直接采样时，构造一条马尔可夫链，使其稳态分布为 $\pi(x)$。常见算法：

• Metropolis-Hastings 算法（1953/1970）：提出候选点，按接受概率决定是否移动
• Gibbs 采样：依次对每个维度条件采样，适合有解析条件分布的模型

蒙特卡洛树搜索（MCTS）：

在游戏 AI 中，MCTS 将蒙特卡洛模拟与树搜索结合：

1. 选择：从根节点用 UCB 策略选择最有前途的子节点
2. 扩展：添加新的叶节点
3. 模拟：从叶节点随机模拟到终局
4. 回传：将胜负结果反向传播更新统计值

AlphaGo（2016）将 MCTS 与深度神经网络结合，击败人类围棋冠军。

UCB 公式：探索与利用的定价——MCTS 的"选择"步要在每个节点回答一个两难：是走当前胜率最高的着法（利用），还是试很少走过的着法（探索）？UCT 算法（Kocsis 与 Szepesvári，2006）把树搜索还原成一系列多臂老虎机问题，用 UCB1 公式（Auer、Cesa-Bianchi 与 Fischer，2002）给每个子节点打分：

$$\text{score}_j = \bar{x}_j + C\sqrt{\frac{\ln N}{n_j}}$$

$\bar{x}_j$ 是子节点 $j$ 的平均收益（利用项），$n_j$ 是它被访问的次数，$N$ 是父节点的总访问次数。探索项随 $n_j$ 增大而缩小、随 $\ln N$ 缓慢增大——一个节点被冷落得越久，探索加分越高，迟早会被重新试一试；但如果它每次都输，利用项会把它压下去。对数增长保证"没有节点被永久遗忘，也没有坏节点被反复纠缠"：理论上的遗憾（regret）只随时间对数增长，这是多臂老虎机问题能达到的最优量级。MCTS 因此天然把大部分模拟预算花在最有前途的分支上，同时又不过早锁死冷门妙手——这正是它在围棋这种分支因子巨大的游戏中胜过传统剪枝搜索的原因。

MCMC 为什么有效：细致平衡#

MCMC 的目标是从一个只知道"相对形状"的分布 $\pi(x)$ 中抽样——比如贝叶斯后验，其归一化常数往往是算不出来的高维积分。办法是造一条马尔可夫链，让它的长期驻留分布恰好是 $\pi$。怎么保证这一点？

关键在于细致平衡条件（Detailed Balance）：

$$\pi(x)\,P(x \to y) = \pi(y)\,P(y \to x)$$

它要求状态 $x$ 流向 $y$ 的"概率流"与 $y$ 流向 $x$ 的完全相等——就像两座城市之间双向车流相等，各自的人口就不再变化。满足细致平衡的链，$\pi$ 一定是它的平稳分布（充分但非必要条件）。

Metropolis-Hastings 的接受概率就是冲着这个条件设计的。设提议分布为 $q(y \mid x)$，取接受率

$$\alpha(x \to y) = \min\left(1,\; \frac{\pi(y)\,q(x \mid y)}{\pi(x)\,q(y \mid x)}\right)$$

若 $y$ 方向"欠流"（$\pi(y)\,q(x \mid y) > \pi(x)\,q(y \mid x)$），就无条件接受以补齐流量；反之则以恰好使两向流量相等的概率接受。Metropolis（1953）处理了提议分布对称的情形，Hastings（1970）把它推广到任意提议分布——后者才是工程上真正使用的形式。

这个构造有一个深远的副产品：接受率只含 $\pi$ 的比值，归一化常数在除法中消掉了。正是这一点，让"知道形状但算不出总面积"的分布变得可以采样，贝叶斯统计因此在 1990 年代之后从理论工具变成了日常计算工具。

细致平衡比“最终会收敛”更强：它要求每一对状态之间的概率流都抵消，而不只是每个状态的净流入为零。后者称为全局平衡，是平稳分布的定义本身；前者是可逆链的充分条件，工程上好验证，所以 Metropolis–Hastings 选了它。不满足细致平衡的链仍可能有正确的平稳分布，只是证明和应用都更难，日常算法很少走那条路。

1953 年，Metropolis、Rosenbluth 夫妇与 Teller 夫妇在洛斯阿拉莫斯的 MANIAC 上对二维刚性圆盘做状态方程计算，接受规则按玻尔兹曼因子 $\exp(-\Delta E/kT)$ 来写。那是细致平衡第一次变成可运行的机器程序。Hastings（1970）把提议分布推广到不对称情形之后，同一套接受率才直接服务于 贝叶斯推断：后验往往只知道形状、算不出归一化常数，但比值已经够用。

链一旦可逆，并不自动等于已经采到独立样本。相邻状态高度相关时，名义上的 $N$ 个点可能只相当于几十个有效样本，误差棒会被系统性低估。诊断因此要看自相关时间、烧入期、以及多条链是否混到同一区域，而不是看接受率是否落在某个坊间传说的最佳区间。接受率太高通常说明提议步长太小、链在原地蹭；太低则几乎不移动——两者都是混合失败，都与赌桌上的手气无关。

应用版图#

代价与争议#

收敛慢：蒙特卡洛的误差以 $1/\sqrt{N}$ 衰减，比许多数值方法慢。对低维光滑问题，传统数值积分（高斯积分等）更快；蒙特卡洛的优势只在高维或不规则问题中显现。

方差问题：如果采样分布与目标分布差异很大，重要性采样权重可能出现极端值，导致估计方差爆炸（"权重退化"）。

MCMC 的混合问题：马尔可夫链到达稳态分布需要"烧入期（Burn-in）"，对于多峰分布，链可能长时间困在一个峰周围而不探索其他区域。

伪随机数的质量：计算机产生的是伪随机数，其质量直接影响模拟结果。低差异序列（Quasi-Monte Carlo）用确定性序列代替随机数，收敛速度可达 $O(\log^d N / N)$，远快于 $1/\sqrt{N}$。

独立样本的蒙特卡洛误差按 $1/\sqrt{N}$ 下降；MCMC 的有效样本量是 $N$ 除以某种自相关因子，下降得更慢。把链式样本当成独立撒点来报置信区间，是把频率估概率的前提用错了地方。准蒙特卡洛用低差异序列加快的是独立积分，并不能自动修好一条困在单峰里的马尔可夫链。

大数定律：为什么"平均"就能逼近#

蒙特卡洛的全部合法性来自两条极限定理的分工。

大数定律（Law of Large Numbers）说：独立同分布样本的均值，随样本量增加几乎必然收敛到真实期望。这一条把"估算"变成了"算法"——只要把想算的量（积分、概率、期望收益）改写成某个可以抽样的分布下的期望，剩下的事就是抽样、取平均、等待收敛。所以蒙特卡洛方法真正的技术含量从来不在"随机撒点"，而在第一步：构造那个分布。重要性采样、MCMC、分层采样，全部都是围绕"让样本均值更快逼近目标期望"的分布工程。

中心极限定理则回答第二个问题：要等多久？

误差分析：中心极限定理的保证#

蒙特卡洛积分的误差由中心极限定理（CLT）支撑：$N$ 个独立同分布样本的均值，其误差分布近似正态分布，标准差为 $\sigma / \sqrt{N}$（$\sigma$ 是被积函数的标准差）。

这意味着：

• 误差以 $1/\sqrt{N}$ 收敛：精度提高 10 倍需要 100 倍样本
• 误差与维度无关：$d = 1000$ 和 $d = 1$ 的积分，同样的 $N$ 给出同样的精度（这是相对于传统数值积分的决定性优势）
• 可以给出置信区间：$N$ 个样本后，估计误差的 95% 置信区间为 $\pm 1.96 \sigma / \sqrt{N}$

对比传统数值积分（如高斯-勒让德积分），$d$ 维光滑函数精度达到 $\epsilon$ 需要 $O(\epsilon^{-1/d})$ 个评估点——指数依赖维度，称为"维度诅咒"。蒙特卡洛打破了这个诅咒。

历史背景：曼哈顿计划与赌场#

"蒙特卡洛"这个代号由尼古拉斯·梅特罗波利斯（Nicholas Metropolis）提议，灵感来自乌拉姆的叔父常去赌博的摩纳哥蒙特卡洛赌场。赌场的轮盘赌是最直观的随机过程之一。

代号借用赌场，只是为了强调方法依赖随机数，不是把轮盘策略搬进实验室。乌拉姆的纸牌思路是计数与比例，梅特罗波利斯的中子问题是碰撞的条件概率；两者都是用频率去估一个定义清楚的概率，没有一条是在教人如何战胜庄家。

最初的应用是在曼哈顿计划中模拟中子在裂变材料中的随机游走：中子轰击铀核，可能被吸收、散射或引发新的裂变。每次碰撞都是随机的，解析求解不可能，但用随机采样估计链式反应的临界质量是完全可行的。尼古拉斯·梅特罗波利斯（Nicholas Metropolis）是早期最重要的贡献者之一，他在 ENIAC 上实现了最初的蒙特卡洛模拟程序（1948 年）。

现代变体速览#

粒子滤波（Particle Filter / Sequential Monte Carlo）：用一组带权重的粒子（随机样本）近似跟踪随时间演化的概率分布，广泛用于机器人定位（SLAM）、语音识别解码和金融时序状态估计。

扩散模型（Diffusion Models）中的 MCMC：Stable Diffusion、DALL-E 等生成模型的训练和推理过程，本质上是在高维图像空间中用近似 MCMC 采样——从纯噪声逐步"去噪"到真实图像，是蒙特卡洛思想在深度学习时代的最新体现。

跨域连接#

• 中心极限定理：估计误差按样本标准差除以样本数的平方根衰减，而这个速率与维度无关。两条推论都很硬：精度提高十倍要一百倍样本，所以在低维光滑问题上它打不过求积公式；而传统求积的代价随维度指数增长，所以高维几乎只剩它。定理还顺带给出置信区间，这是确定性近似给不出的。
• 随机化算法：这里的随机性不是权宜之计，它买到的是可证明的东西——无偏、方差有界、置信度可量化。判据是"验证比求解便宜多少"：能廉价判定单个样本好坏时，采样划算；若每个样本的评估本身极贵，方差的代价就压过一切，该做的是降方差而不是加样本。
• 伊辛模型：链式采样正是为统计力学而生，细致平衡条件保证稳态分布就是目标分布。但临界点附近会出现临界慢化：自相关时间随系统尺度发散，名义上百万个样本可能只含几十个独立样本，误差棒因而被系统性低估。这是所有链式采样的通病，诊断办法是先估自相关时间再报误差。
• 反应速率：速率方程默认分子数大到可以当作连续浓度，一旦拷贝数只有几十个，涨落就不再是噪声而是主角。此时要按倾向函数抽样下一次反应的时刻与种类，逐事件推进。差别可检验：确定性方程给出单一轨迹，随机模拟给出分布，而低拷贝数的基因表达实验数据确实呈分布而非单值。
• 期权、衍生品与布莱克-斯科尔斯：路径依赖期权没有闭式解，定价只能模拟大量价格路径再取贴现期望。平方根的收敛速度决定了实务做法：多一位精度要百倍算力，所以交易台靠对偶变量、控制变量与低差异序列降方差，而不是买机器。极端分位数更麻烦——尾部样本天然稀少，这正是重要性采样存在的理由。

参考文献#

• Metropolis, N. & Ulam, S. The Monte Carlo Method. Journal of the American Statistical Association 44(247), 335–341 (1949).
• Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H. & Teller, E. Equation of State Calculations by Fast Computing Machines. Journal of Chemical Physics 21(6), 1087–1092 (1953). https://doi.org/10.1063/1.1699114
• Geman, S. & Geman, D. Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images. IEEE TPAMI 6(6), 721–741 (1984).
• Silver, D. et al. Mastering the Game of Go with Deep Neural Networks and Tree Search. Nature 529, 484–489 (2016).
• Hastings, W. K. Monte Carlo Sampling Methods Using Markov Chains and Their Applications. Biometrika 57(1), 97–109 (1970).
• Auer, P., Cesa-Bianchi, N. & Fischer, P. Finite-Time Analysis of the Multiarmed Bandit Problem. Machine Learning 47(2–3), 235–256 (2002).
• Kocsis, L. & Szepesvári, C. Bandit Based Monte-Carlo Planning. ECML 2006, pp. 282–293.

延伸阅读#

• Robert, C. & Casella, G. Monte Carlo Statistical Methods. 2nd ed. Springer, 2004.