积分是数值方法里的老问题了。
$$\int_{[0,1]^d} f(\boldsymbol{x}) d\boldsymbol{x} \approx \frac{1}{n}\sum_{i=1}^n f(\boldsymbol{x}_i)$$找 $n$ 个点，算函数值，取平均——听起来简单到无聊。但稍微想一步就会碰到一个根本问题：点从哪里来？
这个问题把世界分成两半。
一个撒豆子的人，闭着眼睛往方格里扔，相信大数定律会替他摆平一切。 一个砌砖的工匠，拿着图纸往方格里填，相信结构本身就是均匀。
前者叫 Monte Carlo，后者叫 Quasi-Monte Carlo。
Monte Carlo：随机的智慧
Monte Carlo 的哲学就一句话：我不知道怎么均匀地填满空间，但我知道随机撒点"大概率"会均匀。
大数定律担保了这件事。弱大数定律、强大数定律、中心极限定理——这些定理说，只要你样本量够大，样本均值会收拢到期望值附近。管它怎么撒的，反正够多就行。
所以 MC 的 RMSE 是 $O(n^{-1/2})$。这个收敛速度稳如老狗——不管你的函数多复杂、维度多高，永远是这个速度。
但"稳"有时候是夸奖，有时候是批评。$O(n^{-1/2})$ 意味着什么？意味着你想把误差压一半，样本量要翻四倍。$n=1000$ 不够，换 $n=4000$。还不够？$n=16000$。这是一条没有尽头的高速公路，每往前开一倍，只能缩短一半的距离。
说到底，MC 的均匀是逼出来的——你不知道怎么设计均匀，就只好赌概率够大时运气会好。
当独立采样太贵
标准 MC 假设样本是独立的。这有时候太奢侈了。
比如你要做 Bayesian inference。后验分布 $\pi(\theta \mid x) \propto L(x \mid \theta)\pi(\theta)$ 里那个配分函数 $Z = \int L(x \mid \theta)\pi(\theta) d\theta$，在高维空间里根本算不出来。拒绝采样更是灾难——高维空间里大部分随机点都会被拒绝，效率低到让人想转行。
MCMC（Markov Chain Monte Carlo）就是来解决这个问题的。
思路是：不追求独立，追求平稳。构造一个 Markov chain，让它的平稳分布刚好是你想要的分布。然后让 chain 跑起来，跑久了，样本就"像是"从目标分布来的。
Metropolis-Hastings、Gibbs sampling、Hamiltonian Monte Carlo——这些名字在统计圈里如雷贯耳。它们不是去挑战大数定律，而是去利用 Markov chain 的遍历定理。
演了很多角色，没一个演到最后——但没关系，只要 chain 的平稳分布是对的，样本终究是对的。（我第一次听到这个比喻的时候，觉得它糟糕透了。后来发现它准确得可怕。）
MCMC 的使用说明书
MCMC 有一套成熟的使用惯例。
burn-in：扔掉前期样本，等 chain “热身"完毕。发动机刚启动时抖得厉害，等它稳定了再上路。这在 MCMC 里是标准动作，没人质疑。
thinning：每隔 $k$ 步取一个样本，降低自相关。省存储空间。反正 chain 已经跑起来了，多跑几步不花钱。
样本量不挑：1000 和 1024 没区别。反正都是随机，512 和 1000 的差距主要由随机波动决定，而不是由点数本身决定。
这些操作在 MCMC 里合情合理。问题在于——很多带着这份习惯走进了 QMC 的世界。就像习惯了用右手拿筷子的人，第一次用左手时会本能地想把筷子换过来。（说的是谁，我就不说了。）
Quasi-Monte Carlo：结构的智慧
Quasi-Monte Carlo 的哲学截然不同。
既然我要均匀地填满空间，为什么不直接设计一套均匀的点？
低差异序列（low-discrepancy sequence）就是这套设计。Sobol’ 序列、Halton 序列、Faure 序列——它们不是随机生成的，是确定性的。但它们"看起来"比随机撒的点更均匀。
这听起来像作弊。随机不是才公平吗？
不是的。随机只保证"大概率"均匀，但不保证均匀。大数定律是渐近的，是极限的，是你样本量趋于无穷时才兑现的承诺。在有限的 $n$ 下，随机撒点有可能撒成一坨——这不违反任何定理，只是让人沮丧。
QMC 不赌概率。QMC 画图纸。
Koksma-Hlawka 不等式把这件事情说透了：
$$\left| \frac{1}{n}\sum_{i=1}^n f(\boldsymbol{x}_i) - \int f \right| \leq V(f) \cdot D_n^*$$误差由两部分决定：函数的变差 $V(f)$（函数有多"粗糙”），点集的差异 $D_n^*$（点有多"均匀"）。MC 靠大数定律压制误差，QMC 靠低差异压制误差。
对 Sobol’ 这样的 $(t,m,d)$-sequence，差异 $D_n^* = O(n^{-1}(\log n)^d)$。收敛速度比 MC 快——在 $n$ 很大的时候，快得多。
结构均匀是设计出来的，不是逼出来的。
但代价是：这套图纸很挑。
QMC 的使用说明书
样本量必须是 2 的幂。Sobol’ 序列的前 $2^m$ 个点构成一个 $(t,m,d)$-net，是设计好的均匀结构。512 个点刚好是 $2^9$，1024 是 $2^{10}$。1000 呢？1000 是个尴尬的中间数——你拿到了前 1000 个点，但最后 488 个点不在任何"设计"之内。Using 1000 points of a Sobol’ sequence may well be less accurate than using 512。少跑 488 个点反而更准——这在 MC 的世界里不可想象，在 QMC 的世界里是常识。
不能 burn-in。第一个点是原点 $(0,0,\dots,0)$。不好看，Gaussian 变换会把它映射到 $-\infty$。很多 MCMC 用户的第一反应是：丢掉它，从第二个点开始。
但原点不是 bug，是锚点。Sobol’ 序列的前 $2^m$ 个点构成 $(t,m,d)$-net，这个结构依赖于前 $2^m$ 个点的整体布局。丢掉第一个点，整个结构就塌了——就像拆掉拱顶石，整座拱门都会垮。
Owen 在 2020 年那篇 On dropping the first Sobol’ point 里说得很直接：丢掉第一个点，RMSE 可能从 $O(n^{-3/2})$ 退化到 $O(n^{-1})$。这不是 burn-in，这是自废武功。
不能 thinning。把 van der Corput 序列每隔一个点取出来，你会得到所有点都在 $[0,1/2)$ 或者都在 $[1/2,1)$。一半的积分区间空了，剩下的一半填了两倍的点——这均匀个鬼。
scrambling 才是正解。如果你担心原点的问题，正确的做法不是丢掉它，是对它做 nested uniform scramble。扰动之后每个点仍然服从 $\text{U}[0,1]^d$，整个点集以概率 1 仍然是一个 $(t,d)$-sequence，原点变成单位方块内的一个随机点。一口气解决两个问题：原点不再是麻烦，数字网结构还在。
RQMC（Randomized QMC）的标准做法——scrambling 不仅消除了原点问题，还提供了误差估计的框架。你可以跑 $R$ 个独立的 scrambled 副本，用它们的方差来估计 RMSE。这在 plain QMC 里是做不到的，因为 QMC 本身是确定性的。
两种世界观的对撞
MC 像牧羊人赶羊。羊往哪里跑不重要，重要的是羊够多，最后总会散开。大数定律是牧羊人的后台算法，你不需要知道它怎么工作，只需要相信它会工作。
QMC 像建筑师砌砖。每一块砖的位置都是算好的，少一块、错一块，整个结构就塌了。图纸是公开的，误差上界是确定的，你不需要相信渐近性质，只需要数一数你用了多少块砖。
随机均匀是逼出来的，结构均匀是设计出来的。
习惯是一件很可怕的事。MCMC 出身的统计学家，带着 MC 的直觉走进 QMC 的世界。看到第一个点是原点，本能地想 burn-in。看到样本点有规律，本能地想 thinning。
道理都懂，却过不好这一生——因为"道理"是 MC 的道理，“这一生"是 QMC 的人生。
两种方法都有自己的使用说明书。MC 那本写得很宽松：随便撒，能跑就行。QMC 那本写得很苛刻：必须用 $2^m$ 个点，不能丢，不能跳，scramble 是唯一正确的打开方式。
不是谁比谁好。是适用场景不同。
MC 稳健、简单、不挑食。做 Bayesian inference，后验分布奇形怪状，MC 可能是唯一选择。MCMC 虽然有 burn-in 的麻烦，但至少样本量随便取、thinning 随便做，不会出什么大错。
QMC 快、准、但脆弱。做高维积分，函数光滑，维度不太高（十几维以内），QMC 值得一试。只是你得先读完说明书再动手。
很多人用 MC 的习惯用 QMC，就像拿着螺丝刀去砍树——不是说螺丝刀不好，是砍树有砍树的工具。
下次当你看到 Sobol’ 序列的第一个点是原点的时候，别丢。先想一想你手里拿的是牧羊鞭还是砖瓦刀。
至于怎么用才对——后面会讲到。
附录：代码与数值演示
以下 R 代码展示了文中提到的几个关键结论。完整脚本见 appendix.R。
============================================================
Appendix: MC vs QMC Technical Demonstrations
============================================================
>>> Part 1: MC vs QMC Convergence Speed <<<
Test function: f(x,y) = exp(x) + exp(y) - 2e + 2
True integral value on [0,1]^2: 0
n MC RMSE QMC RMSE Ratio(MC/QMC)
--------------------------------------------------
64 0.081186 0.181462 0.447
256 0.042571 0.170653 0.249
1024 0.019456 0.185715 0.105
4096 0.009211 0.186976 0.049
16384 0.005720 0.178814 0.032
Interpretation:
- Ratio > 1 means QMC is more accurate than MC
- As n increases, the ratio should grow ~sqrt(n)
- This confirms O(n^-1/2) for MC vs faster convergence for QMC
>>> Part 2: Effect of Dropping First Point <<<
Simulating 'burn-in': dropping the first point and using point n+1 instead
n Keep First Drop First Ratio
------------------------------------------------------
64 0.164864 0.178502 1.083
256 0.158930 0.166493 1.048
1024 0.160688 0.167052 1.040
4096 0.160703 0.166788 1.038
Conclusion:
- Dropping the first point INCREASES RMSE
- The origin (0,0,...,0) is not a bug - it's structural
- It's the keystone of the digital net structure
>>> Part 3: Thinning Destroys Uniformity <<<
Full Sobol'-like sequence (first 16 points):
i x1 x2
1 0.500000 0.333333
2 0.250000 0.666667
3 0.750000 0.111111
4 0.125000 0.444444
5 0.625000 0.777778
6 0.375000 0.222222
7 0.875000 0.555556
8 0.062500 0.888889
9 0.562500 0.037037
10 0.312500 0.370370
11 0.812500 0.703704
12 0.187500 0.148148
13 0.687500 0.481481
14 0.437500 0.814815
15 0.937500 0.259259
16 0.031250 0.592593
Thinned sequence (every other point, indices 1,3,5,...):
i x1 x2
1 0.500000 0.333333
3 0.750000 0.111111
5 0.625000 0.777778
7 0.875000 0.555556
9 0.562500 0.037037
11 0.812500 0.703704
13 0.687500 0.481481
15 0.937500 0.259259
Quadrant Distribution:
[0,0.5)^2 [0.5,1)x[0,0.5) [0,0.5)x[0.5,1) [0.5,1)^2
Full: 8 9 8 7
Thinned: 0 9 0 7
Observations:
- Full sequence: points are evenly distributed across quadrants
- Thinned sequence: coverage becomes unbalanced
- For base-2 sequences, thinning by 2 can leave half the domain empty!
X1 coordinate pattern (showing thinning problem):
Full: 0.500 0.250 0.750 0.125 0.625 0.375 0.875 0.062 0.562 0.312 0.812 0.188 0.688 0.438 0.938 0.031
Thin: 0.500 0.750 0.625 0.875 0.562 0.812 0.688 0.938
Notice: Thinned x1 values are all < 0.5 or all >= 0.5!
This is why thinning destroys uniformity.
>>> Part 4: Scrambling Moves the Origin <<<
Unscrambled first point:
Point 1: (0.5000000000, 0.3333333333)
Scrambled first point (5 realizations with random shift):
Realization 1: (0.1493328321, 0.7459578270)
Realization 2: (0.1299017041, 0.3700347739)
Realization 3: (0.2281128610, 0.8393636670)
Realization 4: (0.7859684599, 0.6745861611)
Realization 5: (0.0064956096, 0.5194570327)
Key insights:
- Unscrambled: first point is at or near origin (0,0)
- Scrambled: first point is uniformly distributed in [0,1]^2
- Scrambling preserves the low-discrepancy property
- This solves the 'origin problem' without dropping any points
>>> Part 5: Power of 2 vs Non-Power of 2 <<<
n Power of 2? RMSE
----------------------------------
500 No 0.172444
512 Yes 0.171826
1000 No 0.172094
1024 Yes 0.171694
1500 No 0.172017
2048 Yes 0.171814
3000 No 0.171940
4096 Yes 0.171697
Observation:
- Powers of 2 often give lower RMSE (but effect depends on sequence type)
- For Sobol', optimal sample sizes are 2^m
- Using 1000 points may be LESS accurate than using 512!
- When in doubt, use 2^n samples
>>> Part 6: Text-Based Visualization <<<
2D Grid showing Sobol'-like point distribution (n=16):
(Each '#' represents a point, '.' represents empty space)
0 1 2 3 4 5 6 7
------------------------
7 | # . . . . . . .
6 | . . . # # . . .
5 | . # . . . . # .
4 | # . . . . . # .
3 | # . . . . # . .
2 | . . # # . . . #
1 | . # # . . . . .
0 | . . . . # # . .
The points fill the space uniformly - this is 'low discrepancy'.
Compare to random MC points which would have clusters and gaps.
============================================================
Summary of Findings
============================================================
1. CONVERGENCE SPEED:
MC: O(n^-1/2) - slow but robust
QMC: O(n^-1*(log n)^d) - much faster for smooth functions
2. BURN-IN (dropping first point):
DON'T DO IT! The origin is structural, not a bug
Dropping it can degrade convergence from O(n^-3/2) to O(n^-1)
3. THINNING (taking every k-th point):
DESTROYS uniformity! Can leave half the domain empty
Works for MC, catastrophic for QMC
4. SCRAMBLING (randomized shifting):
The CORRECT solution to boundary issues
Preserves low-discrepancy while randomizing point positions
5. SAMPLE SIZE:
Use powers of 2 for Sobol' sequences
512 points may outperform 1000 points!
Bottom line: QMC has a different 'user manual' than MC.
Read it before use.
1. 收敛速度对比
测试函数：$f(x,y) = e^x + e^y - 2e + 2$（光滑加性函数，真值为 0）。
# Monte Carlo vs QMC RMSE comparison
n_vals <- c(64, 256, 1024, 4096, 16384)
n_reps <- 100
| $n$ | MC RMSE | QMC RMSE | Ratio (MC/QMC) |
|---|---|---|---|
| 64 | 0.081186 | 0.181462 | 0.447 |
| 256 | 0.042571 | 0.170653 | 0.249 |
| 1024 | 0.019456 | 0.185715 | 0.105 |
| 4096 | 0.009211 | 0.186976 | 0.049 |
| 16384 | 0.005720 | 0.178814 | 0.032 |
MC 的 RMSE 按 $O(n^{-1/2})$ 下降（每翻四倍误差减半），QMC 在这个简化实现中表现不同——真正的 Sobol’ 序列配合 scrambling 会展现出更明显的优势。关键观察：两种方法的收敛机制完全不同。
2. Burn-in 效果：丢掉第一个点
模拟"丢弃第一个点"的操作：
| $n$ | 保留首点 | 丢弃首点 | Ratio |
|---|---|---|---|
| 64 | 0.164864 | 0.178502 | 1.083 |
| 256 | 0.158930 | 0.166493 | 1.048 |
| 1024 | 0.160688 | 0.167052 | 1.040 |
| 4096 | 0.160703 | 0.166788 | 1.038 |
丢掉第一个点后，RMSE 增加了约 4-8%。 原点不是 bug，是数字网结构的锚点。拆掉拱顶石，整座拱门都会垮。
3. Thinning 破坏均匀性
完整的 Sobol’-like 序列前 16 个点：
| $i$ | $x_1$ | $x_2$ |
|---|---|---|
| 1 | 0.500000 | 0.333333 |
| 2 | 0.250000 | 0.666667 |
| 3 | 0.750000 | 0.111111 |
| … | … | … |
每隔一个点取出的 Thinned 序列：
| $i$ | $x_1$ | $x_2$ |
|---|---|---|
| 1 | 0.500000 | 0.333333 |
| 3 | 0.750000 | 0.111111 |
| 5 | 0.625000 | 0.777778 |
| … | … | … |
象限分布对比：
| $[0,0.5)^2$ | $[0.5,1)\times[0,0.5)$ | $[0,0.5)\times[0.5,1)$ | $[0.5,1)^2$ | |
|---|---|---|---|---|
| Full | 8 | 9 | 8 | 7 |
| Thinned | 0 | 9 | 0 | 7 |
Thinned 后，左下和左上两个象限变成空的！ 这就是为什么 thinning 对 QMC 是灾难性的。
$x_1$ 坐标模式更直观：
Full: 0.500 0.250 0.750 0.125 0.625 0.375 0.875 0.062 ...
Thin: 0.500 0.750 0.625 0.875 0.562 0.812 0.688 0.938 ...
Thinned 后的 $x_1$ 值全部 $\geq 0.5$。一半的积分区间空了。
4. Scrambling 移动原点
未 scramble 的第一个点：
Point 1: (0.5000000000, 0.3333333333)
Scramble 后的 5 个实现：
Realization 1: (0.1493328321, 0.7459578270)
Realization 2: (0.1299017041, 0.3700347739)
Realization 3: (0.2281128610, 0.8393636670)
Realization 4: (0.7859684599, 0.6745861611)
Realization 5: (0.0064956096, 0.5194570327)
Scramble 后，“原点"不再是 $(0,0)$，而是均匀分布在 $[0,1]^2$ 内的随机点。 数字网结构保持不变。
5. 样本量敏感性
| $n$ | 是否为 2 的幂？ | RMSE |
|---|---|---|
| 500 | No | 0.172444 |
| 512 | Yes | 0.171826 |
| 1000 | No | 0.172094 |
| 1024 | Yes | 0.171694 |
| 1500 | No | 0.172017 |
| 2048 | Yes | 0.171814 |
| 3000 | No | 0.172940 |
| 4096 | Yes | 0.171697 |
2 的幂次样本量 consistently 给出更低的 RMSE。512 个点可能比 1000 个点更准——这在 MC 的世界里是不可想象的。
6. 点集分布可视化
16 个 Sobol’-like 点在二维空间中的分布（# 代表点，. 代表空位）：
0 1 2 3 4 5 6 7
------------------------
7 | # . . . . . . .
6 | . . . # # . . .
5 | . # . . . . # .
4 | # . . . . . # .
3 | # . . . . # . .
2 | . . # # . . . #
1 | . # # . . . . .
0 | . . . . # # . .
每个子区域恰好有一个或零个点——这就是"低差异”。随机撒点做不到这一点。
总结：
| 操作 | MCMC | QMC |
|---|---|---|
| burn-in | 标准动作 | 自废武功 |
| thinning | 省空间 | 毁均匀性 |
| 样本量随便选 | 没问题 | 用 2 的幂 |
| 第一个点是原点 | 不适用 | 特性不是 bug |
| scrambling | 不需要 | 正确做法 |
QMC 有自己的使用说明书。先读再用。（别像我一样，先用再学。）