多层 Monte Carlo | Codeboy's Blog

形式陈述

目标为固定常数 $\mu=EP$ ，但实际只能模拟越来越精细的近似 $P_0,P_1,\ldots$ 。设相关变量平方可积，定义 $\Delta_0=P_0$ ， $\Delta_\ell=P_\ell-P_{\ell-1}$ ， $\ell\ge1$ 。同一层差内的两个近似必须具有各自正确的边缘分布，并使用为降差值方差设计的耦合；不同层的样本池、同层不同重复之间相互独立。

对确定的 $L$ 和整数 $N_\ell\ge1$ ，各层用普通MC均值估计层差期望，最终估计量为

\widehat\mu_{ML}=\sum_{\ell=0}^L\frac1{N_\ell}\sum_{i=1}^{N_\ell}\Delta_{\ell i}.

望远镜恒等式给 $E\widehat\mu_{ML}=EP_L$ ，而不是通常无法精确模拟的 $EP$ 。令 $V_\ell=\operatorname{Var}(\Delta_\ell)$ 、每个层差样本的期望费用 $C_\ell>0$ ，则

\operatorname{MSE}(\widehat\mu_{ML}) =(EP_L-EP)^2+\sum_{\ell=0}^L\frac{V_\ell}{N_\ell},\qquad E\operatorname{Cost}=\sum_{\ell=0}^L N_\ell C_\ell.

这是偏差—方差分解，并没有假定近似误差在每条路径上很小。弱偏差 $|E(P_L-P)|$ 决定最细层，层差方差决定各层的重复次数，两项保证不能互相替代。

固定方差预算的最优连续分配

先假设所有 $V_\ell>0$ ，将 $N_\ell$ 暂当正实数。要求模拟方差不超过 $v>0$ ，定义 $S_L=\sum_{\ell=0}^L\sqrt{V_\ell C_\ell}$ 。Cauchy–Schwarz给

\left(\sum_\ell V_\ell/N_\ell\right) \left(\sum_\ell N_\ell C_\ell\right)\ge S_L^2.

等号需 $N_\ell\propto\sqrt{V_\ell/C_\ell}$ ；令方差约束取等，得到

N_\ell^*=\frac{S_L}{v}\sqrt{\frac{V_\ell}{C_\ell}},\qquad \operatorname{Cost}^*=\frac{S_L^2}{v}.

实际取 $N_\ell=\lceil N_\ell^*\rceil$ ，方差只会下降，费用至多增加 $\sum_\ell C_\ell$ 。若要用样本估计每层方差，应另设 $N_\ell\ge2$ ，此时取整开销仍同阶。已知零方差的层不需依公式分配，但仍须能获取其常量贡献；不能把先导样本碰巧相等当作已知零方差。

几何层级的复杂度及其证明

假设存在与 $\ell$ 无关的正常数，使

|E(P_\ell-P)|\le c_1 2^{-\alpha\ell},\quad V_\ell\le c_2 2^{-\beta\ell},\quad C_\ell\le c_3 2^{\gamma\ell},

其中 $\alpha,\beta,\gamma>0$ 。取 $L$ 使第一项不超过 $\varepsilon/\sqrt2$ ，即 $L=O(\log\varepsilon^{-1})$ 且 $2^L=O(\varepsilon^{-1/\alpha})$ ；再令 $v=\varepsilon^2/2$ 。对足够小的 $\varepsilon$ ，

S_L\le c\sum_{\ell=0}^L2^{(\gamma-\beta)\ell/2}.

若 $\beta>\gamma$ ，该几何和有界；相等时为 $L+1$ ；小于时由末层控制，为 $O(2^{(\gamma-\beta)L/2})$ 。连续费用因此分别为 $O(\varepsilon^{-2})$ 、 $O(\varepsilon^{-2}\log^2\varepsilon^{-1})$ 、 $O(\varepsilon^{-2-(\gamma-\beta)/\alpha})$ 。

取整还要付 $O(2^{\gamma L})=O(\varepsilon^{-\gamma/\alpha})$ 。若

\alpha\ge\tfrac12\min(\beta,\gamma),

这项不会超过各自的主阶，故最终整数方案保持上述三种费用界，并有MSE不超过 $\varepsilon^2$ 。若此条件不成立，仍可使用分配，只是费用上界必须保留额外的 $\varepsilon^{-\gamma/\alpha}$ 项。这个取整边界解释了为何不能把连续最优数小于1的精细层当作“几乎不花钱”。

直觉

粗层承担目标的大部分平均量；细层只估计“再精细一步还差多少”。昂贵的细层可以少做，是因为耦合后的差值小，而不是因为精细模型本身波动小。与共同随机数比较模型差相同，层内希望正相关；层与层的样本池则要独立，才能把方差直接相加。

各层内部细粗输出使用同一随机输入形成差，三个独立样本池产生不同精度的均值后相加；最细层仍有离散偏差 — 层内耦合，层间独立

这不是把总体空间切成几层的分层模拟。MLMC分解的是不同近似精度的期望，望远镜的权重均为1，差值可以为负。粗层期望也未知，不能把它假装成已知均值的控制量。

例子与边界

可复算的五层预算

用一个可解校准模型检验公式： $Z_0,Z_1,\ldots$ 独立标准正态，

P=Z_0+\sum_{k\ge1}2^{-k}Z_k,\qquad P_\ell=Z_0+\sum_{k=1}^\ell2^{-k}Z_k+2^{-\ell}.

级数在 $L^2$ 收敛，目标为零，弱偏差 $2^{-\ell}$ 。同一层差共享已有的 $Z_k$ 后， $\Delta_\ell=2^{-\ell}(Z_\ell-1)$ ，因此 $V_\ell=4^{-\ell}$ ，包括 $V_0=1$ 。不同层差的正式样本池仍重新独立生成。

假设被评估的黑箱求解器按成本表 $C_\ell=2^\ell$ 计费，已包含一对细粗输出。这个费用是题设，不是上述可简化高斯公式的运算复杂度；真实应用必须计时或证明自己的成本。选 $L=4$ ，偏差平方为 $1/256$ ，给模拟方差也分配 $v=1/256$ 。有

S_4=1+2^{-1/2}+2^{-1}+2^{-3/2}+2^{-2} =\frac74+\frac{3\sqrt2}4.

连续公式再向上取整给 $(N_0,\ldots,N_4)=(720,255,90,32,12)$ ，费用为 $2038$ ，模拟方差为

\frac1{720}+\frac1{4\cdot255}+\frac1{16\cdot90} +\frac1{64\cdot32}+\frac1{256\cdot12} \approx0.003877528.

总MSE约 $0.007783778<1/128$ 。相同最细层 $P_4$ 的方差为 $341/256$ ；直接用最细层IID，达到同一模拟方差预算 $v=1/256$ 需341次、按每次16收费共5456。这里比较相同偏差与同一成本约定；没有把MLMC的层差数与普通方法的单输出行数简单相比。

边缘都正确，耦合仍可失败

若层差中的 $P_\ell$ 与 $P_{\ell-1}$ 改用完全独立的 $Z$ ，其期望仍正确，望远镜无偏性不变；但差值方差变为两者方差之和，趋近 $8/3$ ，不再按 $4^{-\ell}$ 衰减。于是原 $\beta=2$ 的收益证书消失。只写“使用同一种子”也不是耦合证明：不同精度程序可能按不同顺序消耗随机数，应对齐实际随机事件或构造粗增量为细增量之和。

另一种失败是对每层只保存 $\bar P_\ell$ ，最后把所有均值直接相加；它估计 $\sum_\ell EP_\ell$ ，而不是 $EP_L$ 。望远镜必须保留相邻差值和边缘一致性。

推论与应用

从理论配额到可解释的实现

先规定误差容许 $\varepsilon$ 、偏差保证及费用口径，再用与正式运行独立的先导样本估计 $V_\ell,C_\ell$ ，选择 $L,N_\ell$ 后冻结正式方案。条件于先导，若层级边缘正确，则正式估计的中心为所选 $EP_L$ ；但若先导估计没有可靠上界，代入后的费用最优性与MSE保证只是规划近似，不能宣称已获得定理中的真常数。

每层用在线均值与方差保存 $\Delta_{\ell i}$ ，满足“该层每增加一个样本，细粗边缘一起完成”的不变量。 $N_\ell\ge2$ 时 $\sum s_\ell^2/N_\ell$ 无偏估计固定方案的模拟方差；它不含离散偏差。少数精细层样本很少时，正态区间还需额外分布论证。报告应分别列估计值、模拟MCSE、最细层偏差上界和实际费用。

看最后一个层差均值很小，并不自动证明剩余偏差小：随机抵消、预渐近层级或错误耦合都可能造成假象。若有可信的几何偏差模型，可据此诊断；没有模型时应明确“经验偏差检查”，而非确定性证书。若同一正式样本不断决定增层和停止，固定配额方差分析也不能直接承诺原置信覆盖。

迁移练习

若 $\alpha=1,\beta=1,\gamma=1$ ，MLMC费用为 $O(\varepsilon^{-2}\log^2\varepsilon^{-1})$ 。若最细模型单次费用为 $O(\varepsilon^{-1})$ 且其方差保持常数量级，普通MC费用为 $O(\varepsilon^{-3})$ 。若通过更强耦合使 $\beta=2$ 而其他条件不变，MLMC变为 $O(\varepsilon^{-2})$ 。这个判断依赖已证明的层差衰减，不能仅凭离散方法的弱收敛阶 $\alpha$ 推出。

参考资料

Michael B. Giles，Multilevel Monte Carlo methods，发表版 Acta Numerica 24，2015，259–328；所阅作者PDF首页排版标注2018，§1.2–1.3、§2.1 Theorem 1、§3.1。本文给出连续分配、三种几何和及取整费用的完整推导，校准模型为本页构造。
Michael B. Giles，Multilevel Monte Carlo Path Simulation，Operations Research 56(3)，2008，607–617，原始路径模拟出处；具体SDE弱强收敛条件不由本页通用成本定理代证。

形式陈述 ​

固定方差预算的最优连续分配 ​

几何层级的复杂度及其证明 ​

可复算的五层预算 ​

边缘都正确，耦合仍可失败 ​

从理论配额到可解释的实现 ​

迁移练习 ​

反向链接