Quasi-Monte Carlo：低差异序列更快收敛

MC 的收敛速率与维度无关，QMC 的不是。所以关于 QMC 的每一个问题最后都变成同一个问题：你的有效维度到底是多少。

第 10 篇 · 共 12 篇约 12 分钟

朴素 Monte Carlo 的误差以 $O(1/\sqrt{N})$ 缩放，无论你采样得多聪明。误差减半要四倍样本，做高精度定价时这很贵。

但这条速率还有另一半，常被忽略：它与维度无关。100 维和 1 维一样是 $1/\sqrt{N}$ 。这是 MC 的保障，也是它的天花板——它对被积函数的结构一无所知，也就无法从结构中占任何便宜。

Quasi-Monte Carlo (QMC) 把伪随机样本换成确定性的低差异序列， $d$ 维积分的误差变成 $O((\log N)^d / N)$ 。注意 $d$ 出现在指数上：这个速率依赖维度。维度低的时候它把 MC 甩开，维度高的时候它自己会先垮掉。

所以关于 QMC 的每一个实际问题——用不用、怎么用、什么时候别用——最后都归结成同一个问题：你的 $d$ 到底是多少。下面这篇文章反复回到这一点。

差异，以及它凭什么控制误差

$[0, 1]^d$ 中的点序列 $x_1, x_2, \ldots, x_N$ 的星差异定义为

D_N^* = \sup_{B} \left|\frac{\#\{i : x_i \in B\}}{N} - \text{Vol}(B)\right|

其中 sup 取遍所有锚在原点的轴对齐盒 $B = [0, u_1] \times \cdots \times [0, u_d]$ 。它度量点填充空间的均匀程度：低差异意味着分布得好，高差异意味着有聚集或有空洞。

把它和积分误差连起来的是 Koksma-Hlawka 不等式：

\left|\frac{1}{N} \sum_{i=1}^N f(x_i) - \int_{[0,1]^d} f(x) \, dx\right| \leq V_{\text{HK}}(f) \cdot D_N^*

右边干净地分成两半。 $V_{\text{HK}}(f)$ 是 $f$ 在 Hardy-Krause 意义下的变差，只跟被积函数有关，对足够平滑的函数（大多数期权收益）它有界。 $D_N^*$ 只跟点集有关，跟被积函数无关。于是提高精度的路径就明确了：换一组差异更低的点。

两类点的差异速率差得很远。伪随机点的 $D_N^* = O(\sqrt{\log\log N / N})$ ，代回去就是熟悉的 $O(1/\sqrt{N})$ ；低差异序列的 $D_N^* = O((\log N)^d / N)$ ，好得多。

不过这个界要带着两条注解读。第一，它常常很松——实际 QMC 误差通常远小于界给出的值，所以它适合用来理解 QMC 什么时候帮得上忙，不适合拿来当误差估计。第二， $(\log N)^d$ 里那个 $d$ 是真的： $d$ 一大，这个因子会把 $1/N$ 的优势吃掉。交叉点出现在多大的 $N$ ，取决于 $d$ 和被积函数的光滑度，中等维度下通常在很小的 $N$ 就完成了。

Sobol 序列

Sobol 序列是金融里用得最多的低差异序列，是 base 2 中的 $(t, s)$ -序列，靠一组精心选择的方向数拿到低差异。

它的四个性质决定了它的地位：确定性，给定方向数序列完全确定，没有随机性；低差异，固定维度 $d$ 下 $D_N^* = O((\log N)^d / N)$ ；生成快，base 2 中的线性递推， $N$ 很大也不吃力；维度容忍度好，到 20-50 维仍然可用。

构造依赖每个比特位置上的方向数 $v_k$ ，它们本身是二进制小数。第 $i$ 个点是

x_i = \bigoplus_{k \geq 1} i_k \, v_k

其中 $i_k$ 是 $i$ 的第 $k$ 个比特， $\oplus$ 是按位异或。方向数被选得让点尽量均匀地填满单位立方——这也是 Sobol 唯一真正需要小心实现的地方，方向数表错一个数，低差异性质就没了。好在大多数数值库（Python 里是 scipy.stats.qmc.Sobol）已经做对了，除非你有特别理由，不要自己写。

实际使用时你只需要指定维度 $d$ 和点数 $N$ ，库返回 $[0,1]^d$ 中的 $N \times d$ 矩阵。一个常被忽略的细节是跳过开头：Sobol 序列前几个点的差异并不好，用之前跳掉几百到上千个点。另外，Sobol 的均衡性质是按 2 的幂定义的，取 $N = 2^m$ 比取 10000 这种整数更能拿到它承诺的均匀度。

Halton、Faure 和其他

Halton 序列把 van der Corput 序列推广到多维：维度 $j$ 用第 $j$ 个素数 $p_j$ （2、3、5、7、11、…）作为 base 做 van der Corput 序列。它简单到只需要进制转换，不需要方向数，差异同样是 $O((\log N)^d / N)$ 。它是 Sobol 的历史前身，低维（1-5 维）问题上仍然好用，也最容易从头实现。

Halton 的问题出在高维：素数越取越大，早期维度之间会出现可见的相关性。 $d > 10$ 时通常 Sobol 赢。

Faure 序列对所有维度用同一个素数 base $p \geq d$ ，是 base $p$ 中 $t = 0$ 的 $(t, s)$ -序列，差异与 Sobol 相当。它的优势是构造更容易，不需要 $\mathbb{F}_2$ 上的本原多项式。金融里不如 Sobol 常见，属于你有特定 base 需求时的备选。

另外两个值得知道的名字：Niederreiter 序列把 Sobol 推广到任意 base，更灵活也更复杂；拉丁超立方不是严格意义上的低差异序列，但能达到类似的方差缩减效果。

至于随机化 QMC——给低差异序列加随机置乱——它不是这份名单上的第四个选项，而是上述任何一个的必要配件。理由见后面那节。

为什么金融积分特别吃这一套

前面说 QMC 的速率依赖维度，而金融问题的名义维度动辄几十上百。听起来 QMC 应该早就出局了。它没有出局，是因为名义维度不是那个进指数的 $d$ 。

大多数金融积分的被积函数在大多数维度上很平，变化集中在少数几个”重要”方向。对欧式期权价格，被积函数是布朗增量的平滑函数，它强烈依赖终端值，而对增量的具体先后顺序几乎无所谓。对路径依赖期权，被积函数名义上依赖所有时间步，实际上主要依赖路径的前几个主成分。

这就是有效维度：真正对方差有贡献的维度数。带 100 个时间步的亚式期权，名义维度 100，但大部分变化落在前 3-5 个主成分上，有效维度就是 3-5。QMC 的收敛速率跑在有效维度上， $O((\log N)^{d_{\text{eff}}} / N)$ ，而不是名义维度上。

金融里的典型量级是：欧式期权 1-3，路径依赖期权（亚式、回望、障碍）3-7，多资产期权 5-20。这几个区间恰好都落在 QMC 明显优于 MC 的范围内。这不是巧合，而是这类问题结构上的性质——它们有一个低维的主导子空间，而 QMC 正是靠占这个便宜活着。

也正因如此，降低有效维度本身就是一种优化手段。识别方差最大的方向并优先采样（也就是做主成分分析），或者用下面这个更常用的构造。

布朗桥：把 $d$ 降下来

标准的布朗运动构造按时间顺序生成增量： $W_{t_1}$ ， $W_{t_2} - W_{t_1}$ ，一直到 $W_{t_n} - W_{t_{n-1}}$ 。QMC 按顺序把这些增量填进坐标，于是有效维度就是时间步数——每一步同等重要，没有哪个坐标特别值得低差异序列去伺候。

布朗桥构造换一个顺序：先采样终端值 $W_T$ ，再在 $W_0$ 和 $W_T$ 之间采样中点 $W_{T/2}$ ，再采样四分位点，如此递归。结果是 QMC 样本按重要性排序：最重要的终端值落在第一个坐标上，而 Sobol 序列恰恰是前几维的均匀性最好。

效果是有效维度从 $n$ 降到大约 $\log_2 n$ 的量级。 $n = 100$ 个时间步，有效维度从 100 掉到个位数。这是经验规律不是定理，但对路径依赖期权，它是可用的最有效的方差缩减手段之一，和 QMC 组合起来还能再叠一层改善。

置乱：确定性的代价与解药

QMC 有个直接的麻烦：样本是确定性的，你没法从单次运行估计误差。而不知道误差就不知道什么时候可以停。

随机化 QMC 解决这件事。给低差异序列加一个随机偏移或置乱，使它在平均意义上保持低差异性质，然后跑多个独立置乱，用跨运行的标准差作为误差估计。这个估计是无偏的，而且不牺牲收敛速率。

最流行的是 Owen 置乱 (1995)：把每个点的每一位数字独立随机化。具体做法是在 base $b$ 中生成 Sobol 点，对每个数字位置加一个在 $\{0, 1, \ldots, b-1\}$ 上均匀的随机数字，得到的就是置乱后的 Sobol 点。scipy.stats.qmc.Sobol 的 scramble=True 就是它，这是金融 QMC 的标准随机化技术。

实操上跑 10-100 个置乱，每个用不同的随机种子，跨运行取均值作价格估计、取标准差作误差估计：

import numpy as np
from scipy.stats import norm, qmc

def qmc_call_price(S0, K, r, sigma, T, n_paths=2**13, n_runs=20, seed=42):
    """European call price via randomized QMC (Owen-scrambled Sobol)."""
    rng = np.random.default_rng(seed)
    prices = []
    for _ in range(n_runs):
        # A fresh scramble per run: the runs must be independent randomizations
        # of the same sequence, not consecutive blocks of one sequence.
        sampler = qmc.Sobol(d=1, scramble=True, seed=int(rng.integers(2**32)))
        u = sampler.random(n_paths).ravel()
        # Apply inverse normal CDF
        Z = norm.ppf(u)
        ST = S0 * np.exp((r - 0.5*sigma**2)*T + sigma*np.sqrt(T)*Z)
        payoff = np.maximum(ST - K, 0)
        prices.append(np.exp(-r*T) * payoff.mean())
    return np.mean(prices), np.std(prices) / np.sqrt(n_runs)

mean, se = qmc_call_price(100, 100, 0.05, 0.20, 1.0)
print(f"QMC price: {mean:.4f} ± {se:.4f}")

这里有个容易写错的地方，值得单独指出：每轮必须新建一个采样器并给不同的置乱种子。如果复用同一个 sampler 反复调 random()，你拿到的是同一条序列的连续片段，它们不是独立的随机化，跨运行的标准差就不是误差估计而是一个没有意义的数。

标定一下量级。同样参数下，贴现收益的标准差约 14.7，所以 8,192 条路径的朴素 MC 标准误差在 0.16 附近。上面这个 20 次置乱、每次 8,192 点的 QMC，标准误差落在 $10^{-4}$ 量级，比朴素 MC 小两到三个数量级。这个差距在一维、被积函数只有一个折点的情形下很典型；维度上去、被积函数变糙，差距会缩小。

一个多资产的例子

考虑 $d$ 个相关资产上的篮子看涨期权。朴素 MC 需要在 $d$ 维空间里撒 $N$ 个点； $d = 10$ 时做完 PCA 有效维度大约 5-7，正好在 QMC 的舒适区。

def qmc_basket_call(S0_vec, K, r, sigma_vec, corr, T, n_paths=2**13, n_runs=10, seed=42):
    """Basket call via scrambled QMC with a control variate."""
    d = len(S0_vec)
    rng = np.random.default_rng(seed)
    L = np.linalg.cholesky(corr)
    expected_avg = S0_vec.mean() * np.exp(r*T)   # E[basket] under Q
    prices = []
    for _ in range(n_runs):
        sampler = qmc.Sobol(d=d, scramble=True, seed=int(rng.integers(2**32)))
        u = sampler.random(n_paths)
        Z = norm.ppf(u)
        # Apply correlation
        Z_corr = Z @ L.T
        ST = S0_vec * np.exp((r - 0.5*sigma_vec**2)*T + sigma_vec*np.sqrt(T)*Z_corr)
        basket = ST.mean(axis=1)
        payoff = np.maximum(basket - K, 0)
        # Control variate: the basket level itself, whose mean is known
        beta = np.cov(payoff, basket)[0, 1] / np.var(basket)
        cv_payoff = payoff - beta * (basket - expected_avg)
        prices.append(np.exp(-r*T) * cv_payoff.mean())
    return np.mean(prices), np.std(prices) / np.sqrt(n_runs)

这段代码同时用了三样东西：QMC 采样、Cholesky 相关化、控制变量。相对朴素 MC 的总方差缩减通常在 100-1000 倍量级。

QMC 和其他方差缩减手段是什么关系

QMC 算方差缩减的一种，但它和对偶变量、控制变量、重要性采样在机制上不同：那三种改的是估计量，样本仍然是随机的；QMC 改的是样本，估计量原封不动。

正因为动的是不同的部件，它们可以叠加，而且效果是乘性的。调得好的 QMC + 控制变量 + 对偶变量，相对朴素 MC 拿到三位数以上的方差缩减是常见的。

生产里典型的配方就是把这几件事按顺序装上：底层样本用 Sobol；接一个期望已知的控制变量；合适的话再加对偶变量；路径依赖的用布朗桥把有效维度压下来。这四步没有一步是难的，四步都装上之后，同样的计算预算能买到的精度和朴素 MC 完全不是一个量级。

它什么时候不灵

回到开头那个指数上的 $d$ 。QMC 不是银弹，它的失效模式恰好都能从速率式里读出来。

有效维度太高的时候。 $(\log N)^{d}$ 随 $d$ 增长，而 MC 的 $1/\sqrt{N}$ 岿然不动。固定 $N$ 让 $d$ 增长，QMC 的误差会涨到追上 MC。交叉发生在哪，取决于 $N$ 和被积函数的光滑度： $N$ 一万、有效维度 10 的典型金融问题，QMC 仍然远好于 MC；有效维度 50 时两者可能打平甚至倒挂；超过 100，通常 MC 更好。实用的分界线是有效维度 30 左右：低于它用 QMC，高于它老实用 MC 或换重要性采样、拉丁超立方之类的手段。所以第一件事永远是先知道自己的有效维度，而不是先装 Sobol。

被积函数不够平滑的时候。 Koksma-Hlawka 里的 $V_{\text{HK}}(f)$ 对不连续函数会爆掉。数字期权、正好落在边界上的障碍期权，QMC 的优势明显缩水。平滑化技术能挽回一部分。

样本量太小的时候。 QMC 的优势在大 $N$ 下才显出来。 $N$ 不到一千，它和 MC 差不多； $N$ 上万，差距就拉开了。

以及那个必须自己解决的误差估计。 确定性序列没有自带的不确定度，你要么做随机化，要么去啃解析界——而解析界是松的。实践中只有随机化这一条路。

对大多数金融 MC 问题，这些限制都不构成阻碍：被积函数平滑，有效维度中等，库经过充分测试。

随机化 QMC 的理论，简单一句

Koksma-Hlawka 给的是确定性的最坏情形界，松得没法当误差用。随机化 QMC 有更贴近实际的结果：期望误差满足

\mathbb{E}[|\hat{V}_{\text{rqmc}} - V|] \leq c(d) \frac{V(f)}{N}

其中 $c(d)$ 依赖于 $f$ 的光滑度和维度 $d$ ，中等 $d$ 下的平滑 $f$ 对应的 $c(d)$ 很小。理论基础在 Owen (1995, 1998)。

从业者要记的结论只有一句：用 Owen 置乱，跑 10-100 个置乱，取均值，报标准差。

它在数值积分谱系里的位置

往后退一步看，QMC 本质上是高维数值积分的一种确定性方法，卡在两类方法中间：基于网格的方法（高斯求积、张量积网格）精度高但受维度灾难所限，Monte Carlo 不怕维度但收敛慢。

分工大致是这样：1-3 维，高斯求积、张量积网格或者直接解 PDE 都比 QMC 快；4-20 维，QMC 是最好的选择；20 维以上，Monte Carlo 往往是唯一实际可行的。求解 PDE 这条路在一到三个底层资产上很难被超越，但它不随维度缩放，QMC 缩放得好，于是高维问题默认落到 QMC 手里。

金融里我们通常正好落在中间那一段。这也是少数几个”复杂数值技术确实比简单替代品明显更优”的场合——大多数时候，复杂技术带来的收益还不够抵消它带来的 bug。

并行与生产

QMC 高度可并行：每个置乱互相独立，可以在集群上同时跑上千个。

算一下这笔账，别把它算大了。设单机每秒能跑 100 个置乱、每个置乱 $10^4$ 个点，100 台机器每秒就是 $10^4$ 个置乱、合计 $10^8$ 个样本点。但跨置乱取平均带来的误差下降是 $1/\sqrt{K}$ （ $K$ 为置乱数），所以 100 台机器把标准误差降到单机的十分之一，而不是万分之一——万分之一那个数字来自把方差缩减和样本量混为一谈。真正的收益是两部分相乘：每个置乱内部享受 QMC 相对 MC 的速率优势，置乱之间享受 $1/\sqrt{K}$ 。

即便如此，对需要高精度的定价场景，商用硬件上几秒钟就能到位。成本低，收益实在。

为什么多数人还在用朴素 MC

行业里用 QMC 定价的理由不止速度和精度。同样的计算预算换来更准的价格，这对报价紧的工具直接影响竞争力；不做随机化时 QMC 是确定性的，同样的代码同样的参数给出同样的结果，回测和验证都省心（做了随机化就把种子记下来，效果一样）；而且它对模型、收益结构、维度都不挑，只要有效维度别超过 20 上下，换什么标的都能用。

好处这么明显，实际用的人却不多。原因是可以列清楚的：QMC 在大多数金融课程里不教，很多人根本没听过；朴素 MC 是一行代码，QMC 要 Sobol 序列、置乱、布朗桥，工程量确实更大；随机化又要求多次运行和误差估计，代码更长；不是所有数值库都有像样的 QMC 支持（scipy.stats.qmc 是较近的版本才有的）；最后是文化惯性——“我们一直是这么做的”在成熟组织里是很有力的论据。

这些理由里没有一个是技术性的。如果你在开一个新的 MC 项目，一开始就用 QMC：收益大、成本适中、库支持到位。如果你在维护一套现有 MC 系统，迁移通常值得。

要往下读，Niederreiter (1992) 的 Random Number Generation and Quasi-Monte Carlo Methods 是严格的数学处理，Glasserman (2004) 第 5 章讲金融里的具体应用，Owen (1995, 1998) 是随机化 QMC 的标准参考，Sobol (1967) 是序列本身的原始论文。

最后回到那个贯穿全文的问题：装 Sobol 之前，先估一下你的有效维度。这个数决定了后面所有事情。