对偶抽样 | Codeboy's Blog

形式陈述

目标为 $\mu=Ef(X)$ ，其中 $X\sim P$ ， $0<\sigma^2=\operatorname{Var}(f(X))<\infty$ 。构造一对 $(X,X')$ ，要求两者各自的边缘分布都是 $P$ ，但允许它们相关。独立重复这一对 $m$ 次，定义

A_i=\frac{f(X_i)+f(X_i')}{2},\qquad \widehat\mu_A=\frac1m\sum_{i=1}^m A_i.

边缘正确保证每个 $EA_i=\mu$ ，对与对之间的独立性保证均值方差除以 $m$ 。令 $c=\operatorname{Cov}(f(X),f(X'))$ ，则由和的协方差展开，

\operatorname{Var}(A_i)=\frac{\sigma^2+c}{2},\qquad \operatorname{Var}(\widehat\mu_A)=\frac{\sigma^2+c}{2m}.

若每个函数值都算一次昂贵求值，总预算 $N=2m$ 。同预算的普通Monte Carlo 均值方差为 $\sigma^2/(2m)$ ，所以两者之比为

\frac{\operatorname{Var}(\widehat\mu_A)}{\operatorname{Var}(\widehat\mu_{IID})} =1+\frac c{\sigma^2}=1+\rho.

因此真正的改善条件是输出协方差 $c<0$ ；仅说输入“相反”并不够。相关系数范围给出方差比位于 $[0,2]$ ：最好完全抵消，最差把方差加倍。

常用构造与单调性保证

若 $U\sim\operatorname{Uniform}(0,1)$ ，则 $1-U$ 仍均匀，故可取 $X=\psi(U)$ 、 $X'=\psi(1-U)$ ，其中 $\psi$ 是目标采样变换。必须检查的是组合函数 $g=f\circ\psi$ ，不是孤立地看 $f$ 。

一维中，若 $g$ 单调且平方可积，则 $g(U)$ 与 $g(1-U)$ 的协方差非正。令 $V$ 是 $U$ 的独立同分布副本，恒等式

2\operatorname{Cov}(a(U),b(U)) =E[(a(U)-a(V))(b(U)-b(V))]

由直接展开得到。取 $a(u)=g(u)$ 、 $b(u)=g(1-u)$ 。一个非减、另一个非增，故被积乘积逐点不正；两个都换方向时结论相同。这证明的是非正性，严格降低还需乘积在正概率集合上为负。常数函数没有严格改善。

更一般地，若变换 $T$ 满足 $T(X)\sim P$ 且 $T(T(x))=x$ ，可把 $f$ 写成

f_e(x)=\frac{f(x)+f(Tx)}2,\qquad f_o(x)=\frac{f(x)-f(Tx)}2.

分布不变性给出 $Ef_o(X)=0$ 、 $E[f_e(X)f_o(X)]=0$ 。于是 $\sigma^2=\operatorname{Var}(f_e(X))+\operatorname{Var}(f_o(X))$ ，而对偶法在 $N$ 次求值下的方差为 $2\operatorname{Var}(f_e(X))/N$ 。它消掉反对称部分，同时把保留部分的独立重复次数减半；这解释了改善与失败的共同机制。

直觉

同一对中的偏差最好一个向上、一个向下，先在对内相消，再跨独立对平均。图中框出的才是可重复实验单元；两行输出来自同一随机输入，不能把它们分开当作两次独立试验。

每个独立均匀输入生成U和1-U，两次输出先平均成一个A，再跨独立对平均 — 独立单位是对

共同随机数也用耦合，却通常估计两个方案的差；差的方差中交叉项带负号，因此希望输出正相关。本页估计两个同目标输出的平均，交叉项带正号，因此希望负相关。判断符号要从最终统计量出发。

例子与边界

同样的二次积分，预算相同才有可比性

取 $f(u)=u^2$ ，目标 $1/3$ 。有

E[U^2(1-U)^2]=\frac13-\frac12+\frac15=\frac1{30},\qquad c=\frac1{30}-\frac19=-\frac7{90}.

普通单点方差为 $4/45$ ，故 $\rho=-7/8$ 。一对的均值为

A=\frac{U^2+(1-U)^2}{2}=U^2-U+\frac12,

其方差为 $1/180$ 。在 $N=2m$ 次求值下，估计方差是

\frac1{180m}=\frac1{90N},

相对普通方法的 $4/(45N)$ 减少8倍。控制变量取已知系数1时，单个残差与这里的 $A$ 恰好是同一个多项式；但它每个输入只需一次目标求值，对偶法需要两次，所以同预算收益分别为16倍和8倍。这里规定目标函数按调用计费；若利用这个特殊多项式直接化简掉第二次调用，已经改变了成本模型，应另报优化后的费用。

再取两个输入 $U_1=1/4,U_2=1/2$ 。四个函数输出是 $(1/16,9/16,1/4,1/4)$ ，两个对均值为 $(5/16,1/4)$ ，最后估计为 $9/32$ 。对均值样本方差是 $s_A^2=1/512$ ，故估计均值方差为 $s_A^2/2=1/1024$ ，MCSE 为 $1/32$ 。它不等于理论标准误 $\sqrt{1/360}$ ；只有两对时，方差估计本身也很不稳定，仍不能把一个小的实现值当作精确误差证书。

折返输入不保证折返输出

改成 $f(u)=(u-1/2)^2$ 。此时 $f(1-u)=f(u)$ ，输出完全正相关。目标为 $1/12$ ，单点方差为

E(U-1/2)^4-(1/12)^2=\frac1{80}-\frac1{144}=\frac1{180}.

每一对只是重复同一个输出， $N$ 行只有 $N/2$ 个独立贡献；对偶估计的方差为 $1/(90N)$ ，是 $N$ 次 IID 的两倍。输入 $U$ 与 $1-U$ 确实负相关，但非线性变换抹掉了它们的差别。这是方法的实际失败，不能归咎于随机种子不够好。

若 $f(u)=u$ ，相反地每对均值都等于 $1/2$ ，只用一对便已精确。零方差此时由恒等式保证；它与“有限样本看起来都相等”是不同的证据。

推论与应用

MCSE与运行协议

对 $m\ge2$ 个独立对，计算

s_A^2=\frac1{m-1}\sum_i(A_i-\bar A)^2,\qquad \widehat{\operatorname{MCSE}}=\frac{s_A}{\sqrt m}.

这时 $s_A^2/m$ 无偏估计均值方差。当 $0<\operatorname{Var}(A)<\infty$ ，中心极限定理作用于 $A_1,\ldots,A_m$ ，而不是对内的 $2m$ 个相关输出。正态区间是大样本近似；已知 $A$ 恒定时直接报告代数确定性，不需要除以零学生化。

执行前固定偶数求值预算 $N=2m$ 、采样变换和独立流策略。每轮产生一个新随机输入，生成两种边缘正确的状态，各求一次 $f$ ，立即组成 $A_i$ ，只把该对均值送入在线累加器。不变量是：已完成 $i$ 轮就消耗 $2i$ 次目标调用，累加器含恰好 $i$ 个独立贡献。总目标求值 $2m$ 次、标量更新 $O(m)$ 、流式额外存储 $O(1)$ ；复杂模拟路径的状态空间另计。

固定预算之外，按MCSE目标反复检查会涉及顺序停止问题，不能沿用固定样本正态区间的标称覆盖。若一对中某次模拟失败，不应只保留成功的一半：预先规定重试或失败输出策略，记录整对状态，避免选择性删行改变边缘分布。

自测与答案

某模拟有4000行，由2000个独立输入各产生一对。该对均值样本标准差为0.3。MCSE是多少？答案为 $0.3/\sqrt{2000}$ ，约0.00671；分母不能用 $\sqrt{4000}$ 。
若一对输出的相关系数为 $-0.2$ ，同求值预算能省多少方差？答案为20%，方差比0.8，标准误比 $\sqrt{0.8}$ 。若生成对偶路径的实际开销不同，还应另做时间预算比较，不能把20%直接解释为运行时间节省。

参考资料

Art B. Owen，Chapter 8, “Variance reduction”，§8.2，章页码5–8，式(8.2)–(8.4)，含独立对的方差估计。所阅在线PDF页脚含2018。
J. M. Hammersley 与 K. W. Morton，“A new Monte Carlo technique: antithetic variates”，Mathematical Proceedings of the Cambridge Philosophical Society 52(3)，1956，449–475页，原始方法出处；本文的预算比较、单调性和多项式反例均在上文推导。

形式陈述 ​

常用构造与单调性保证 ​

同样的二次积分，预算相同才有可比性 ​

折返输入不保证折返输出 ​

MCSE与运行协议 ​

自测与答案 ​