随机化拟 Monte Carlo | Codeboy's Blog

形式陈述

设 $f:[0,1)^d\to\mathbb R$ 可积，目标为 $I=\int f(u)\,du$ 。先选一套确定性、覆盖良好的 $n$ 点设计 $a_1,\ldots,a_n$ ，再用一次随机对象 $\omega$ 同时变换整套点，得到 $U_i(\omega)$ 。要求每个 $U_i$ 的边缘均为立方上的均匀分布；整网还应保留所需的低差异或分层结构。单纯把任意点集加噪声并不能自动获得这种结构。

定义一轮估计 $Q_n(\omega)=n^{-1}\sum_i f(U_i(\omega))$ 。边缘均匀性立即给出 $EQ_n=I$ ，不需要网内独立。若 $f\in L^2$ ，记 $v_n=\operatorname{Var}(Q_n)<\infty$ 。使用 $R\ge2$ 个独立且同分布的整网随机化 $\omega_1,\ldots,\omega_R$ ，则

\widehat I_{R,n}=\frac1R\sum_{r=1}^R Q_{n,r},\qquad \operatorname{Var}(\widehat I_{R,n})=\frac{v_n}{R},

\widehat V=\frac1{R(R-1)}\sum_{r=1}^R(Q_{n,r}-\widehat I_{R,n})^2.

$\widehat V$ 无偏估计最终均值的方差； $\sqrt{\widehat V}$ 本身一般不无偏。独立重复单位是整网，不是打印出来的 $Rn$ 行；普通MC均值与样本方差此时作用于 $Q_{n,1},\ldots,Q_{n,R}$ 。把每一网内的样本方差除以 $n$ 会漏掉网内协方差，方向可大可小。具体地，协方差展开给 $v_n=n^{-2}\sum_{i,j}\operatorname{Cov}(f(U_i),f(U_j))$ ，不能只保留对角项。

两种随机化，保留的结构不同

Cranley–Patterson 随机平移取 $\Delta\sim U[0,1)^d$ ，令 $U_i=(a_i+\Delta)\bmod1$ ，逐坐标取小数部分。平移保均匀测度，故每点边缘正确；同一个 $\Delta$ 必须作用于同一网的全部点。逐点使用独立平移虽也无偏，却把设计变成IID均匀点。整体平移保留点的相对位置，但通常不保留数字网的全部进制盒计数。

数字网可用 nested uniform scrambling：以 $b$ 进制写每一坐标，对每个坐标、每个有限原始数字前缀，分别抽一个独立均匀数字置换。一个点的第 $k$ 位用其前 $k-1$ 个原始数字决定的置换映射；共享前缀的点必须共享该置换。对固定点，沿其路径的置换相互独立，每个输出数字均匀，所以无限位输出边缘均匀。另一方面，任意固定长度前缀被双射送到同长度前缀，因此规定进制盒的点数不变。

这里采用半开区间、终止展开补零的约定，排除进制展开的二义性。实际只生成有限位时，采样分布是有限网格；若采样变换在端点奇异，截断位数与零点处理需单独说明，不能把理想连续均匀定理当成浮点误差证明。上述协议也不是所有软件中名为“scramble”的选项的完整定义。

直觉

确定性低差异点负责覆盖，整网随机化负责使期望中心正确并产生可重复实验。两者解决不同问题。每一轮先形成一个积分结果，跨轮波动才回答“换一套合法随机化，我的最终答案会动多少”。

三套各含八点的网分别随机化；每套先形成Q，再跨三个独立Q平均；同网点不能拆成独立重复 — 误差条来自整网重复

低差异不会使所有函数的方差自动降低。若函数振荡与网格同频，整网会一起看到同一个相位，网内平均可能完全没有抵消。必须分析函数与设计的相互作用，而不能只比较点图是否均匀。

例子与边界

线性积分：同样32次求值，精确改善8倍

取一维点 $a_i=i/n$ ， $i=0,\ldots,n-1$ ， $f(u)=u$ 。令 $T=\Delta\bmod(1/n)$ ，则 $T\sim U[0,1/n)$ ，排序后的平移点为 $T+i/n$ ，所以

Q_n=\frac{n-1}{2n}+T,\qquad EQ_n=\frac12,\qquad v_n=\frac1{12n^2}.

取 $n=8,R=4$ ，总求值32次，方差为 $1/3072$ ；32次IID的方差为 $1/384$ ，相差8倍。若四次平移实现值为 $(1,11,21,31)/64$ ，对应的 $Q$ 是 $(29,31,33,35)/64$ ，平均正好为 $1/2$ 。四个 $Q$ 的样本方差为 $5/3072$ ，最终方差估计为 $5/12288$ ，并不等于真实方差 $1/3072$ 。点估计碰巧准确与误差条精确是两回事。

光滑的反例：平移无法消除与网格同频的振荡

仍用 $n$ 个等距点，改成 $f(u)=\sin(2\pi n u)$ ，目标为零。每个点都给出同一个 $\sin(2\pi n\Delta)$ ，故 $v_n=1/2$ 。 $R$ 次整网的方差为 $1/(2R)$ ，而 $Rn$ 次IID的方差为 $1/(2Rn)$ ；平移方法反而坏 $n$ 倍。这个反例为每个给定 $n$ 指定一个函数，不是在断言同一个固定光滑函数随 $n\to\infty$ 永远不收敛。

机制可精确写出来。对有限三角多项式 $f(u)=\sum_k c_k e^{2\pi iku}$ ，几何级数给

\frac1n\sum_{i=0}^{n-1}e^{2\pi iki/n}=\mathbf1\{n\mid k\}.

因此 $Q_n-I=\sum_{k\ne0:n\mid k}c_k e^{2\pi ik\Delta}$ 。不同频率在均匀平移下正交，得到

v_n=\sum_{k\ne0:n\mid k}|c_k|^2.

这是一条具体的混叠证明：网格筛掉非整倍频，却保留整倍频。即使函数无限光滑，也不能省略与所选 $n$ 、频谱及误差常数的关系。

一维scramble与共享平移并不等价

对一维 $(0,m,1)$ 网、 $n=b^m$ ，nested uniform scramble使每个长度 $1/n$ 的区间恰有一点；在这些区间内部，尾部随机数字来自不同前缀的独立置换。因此在忽略点标签后，可以等价地看成每区间一个独立均匀抖动点。

对 $f(u)=u$ ，每层输出方差为 $1/(12n^2)$ ，各层权重 $1/n$ ，按分层Monte Carlo的独立层方差公式，故一整网的方差为 $1/(12n^3)$ 。它比共享平移的 $1/(12n^2)$ 还小 $n$ 倍，因为共享平移让所有区间中的相对位置一起偏左或偏右；独立尾部不会这样同步。

若一维 $f$ 为 $K$ -Lipschitz，同层两个独立副本 $U,U'$ 满足

\operatorname{Var}(f(U))=\tfrac12E(f(U)-f(U'))^2 \le\tfrac{K^2}2E(U-U')^2=\frac{K^2}{12n^2}.

再按独立层求和，得到 $v_n\le K^2/(12n^3)$ 。这里完整证明的是一维分层情形。多维scrambled-net的更快方差率需要固定网参数与混合光滑性等附加条件；不能把本证明直接换成维数 $d$ 就沿用。一般高维数值积分还受有效维数、坐标排序和采样变换的奇异性影响。

推论与应用

执行与报告

先冻结被积函数、采样变换、每网点数 $n$ 和重复数 $R$ 。采用数字网时应遵守其完整网规模，例如 $n=b^m$ ；随意删掉起点、跳过某些点或切成若干相邻块，未必保留原保证。每轮用新的独立随机化状态生成整网，保存一个 $Q_{n,r}$ ；估计值和MCSE只在这些 $Q$ 上计算。总目标调用 $Rn$ 次；点生成、维数与scramble存储另计。

固定 $n$ ，若 $0<v_n<\infty$ ， $R\to\infty$ 时可对独立 $Q$ 使用CLT。有限 $R$ 的 $t_{R-1}$ 区间只有在 $Q$ 正态时精确；一般只是近似，小 $R$ 时不能凭每网有很多点就保证覆盖。一个网只提供一个 $Q$ ，没有跨随机化方差估计。把同一scramble分成若干批，也没有创造独立scramble。

固定总调用 $T=Rn$ 时，若在所研究范围确已证明 $v_n\le c n^{-p}$ 、 $p>1$ ，则方差界为 $cR^{p-1}/T^p$ 。较大 $n$ 有利于这个界，较大 $R$ 有利于误差条的稳定估计，二者存在取舍；没有无条件通用的最优 $R$ 。先用独立试验考察函数与方法，再冻结正式预算，不能挑一次最漂亮的scramble作为最终结果。

自测与迁移

若16个独立scramble的积分结果样本标准差为0.004，则MCSE为0.001，不论每网含多少点。若每网点数翻倍，只凭旧的0.004不能保证标准误再减半，必须有对应方差率或新重复实验。若高频反例换成 $\cos(2\pi(n+1)u)$ ， $n>1$ 时频率不被 $n$ 整除，整网平均恰为零；改变一个频率便改变了结果，这正是需要报告设计的理由。

参考资料

Art B. Owen，Monte Carlo Book: the Quasi-Monte Carlo parts，所阅在线稿页脚2019，Chapter 17，§17.1整网重复、§17.3随机平移、§17.5 nested uniform scrambling。本文的一维方差、32次预算及有限傅里叶混叠均在上文直接推导。
R. Cranley and T. N. L. Patterson，Randomization of Number Theoretic Methods for Multiple Integration，SIAM Journal on Numerical Analysis 13(6)，1976，904–914，随机平移的原始出处；本页未据其全文声称额外结论。
一维独立区间计算复用分层Monte Carlo的方差接口，确定性覆盖及HK变差边界保留在星差异旧页。

形式陈述 ​

两种随机化，保留的结构不同 ​

线性积分：同样32次求值，精确改善8倍 ​

光滑的反例：平移无法消除与网格同频的振荡 ​

一维scramble与共享平移并不等价 ​

执行与报告 ​

自测与迁移 ​

反向链接