45 稀有事件抽样：方差到底改进了多少 · 第3讲

这一页在讲什么

人话版一句话版

不用上一页的精确公式，只用「每个权重 $\leq e^{- b^{2} /2} 」$ 这一条，一行就能证明：

Var_{Q} W \leq e^{- b^{2} /2} \times (伯努利抽样的方差) .

$b = 4$ 时方差至少缩小 $e^{8} \approx 2981$ 倍，精确值约 7000 倍。换句话说：同样的精度，样本数可以少几千倍。

位置：高斯稀有事件抽样三页的最后一页，也是第 5 部分「抽样中的应用」的结尾（后面第 46 页、第 47 页是补充材料）。
小标题 A direct bound for comparison with Bernoulli sampling：一个「直接的界」，用来和伯努利抽样（第 43 页的直接抽样）比较。「直接」指不需要第 44 页的精确计算。
这一页还回答两个问题：
- 样本数的差距随 $b$ 怎样变化？伯努利抽样按指数爆炸，重要性抽样只按线性增长。
- 平移量取 $a = b$ 是不是最好？几乎是。

先补基础

基础补课伯努利抽样（回顾）

每个样本是 $1_{{X_{i} > b}} ，$ $X_{i} \sim N (0, 1) ，$ 它是参数 $p_{b}$ 的伯努利变量：

Var_{P} 1_{{X > b}} = p_{b} (1 - p_{b}), 相对方差 = \frac{p _{b} ( 1 - p _{b} )}{p _{b}^{2}} = \frac{1 - p _{b}}{p _{b}} \approx \frac{1}{p _{b}} .

基础补课有上界的非负变量：平方不超过「上界 × 自己」

若 $0 \leq W \leq c ，$ 则 $W^{2} = W \cdot W \leq c \cdot W$ （把一个 $W$ 换成更大的 $c ，$ 另一个 $W \geq 0$ 不变号）。两边取期望： $E W^{2} \leq c E W 。$

基础补课方差之比 = 样本数之比

由第 37 页， $n$ 个样本平均的均方误差是 $\frac{σ ^{2}}{n} 。$ 两种方法要达到同样的精度，需要的样本数之比就等于单个样本的方差之比。方差缩小 $k$ 倍，就等于样本数节省 $k$ 倍；或者样本数不变，误差缩小 $k$ 倍。

课件原文逐句精读

课件原文Gaussian rare-event sampling: variance improvement

A direct bound for comparison with Bernoulli sampling（以下留白）

中文翻译

蓝条标题：高斯稀有事件抽样：方差的改进。

一个直接的界，用来和伯努利抽样比较（课件留白，见下一节。）

variance improvement：方差的改进，即方差缩小了多少。
direct bound：直接的界，一步就能得到的上界，不求精确。
Bernoulli sampling：伯努利抽样，即在 $P$ 下直接抽样、数命中次数（第 43 页「先补基础」）。

补全课件留白

补充说明

课件此处留白（课堂板书），以下内容由本站根据标准教材补写，记号与本课件保持一致；如与老师课堂写法不同，以老师为准。

A direct bound for comparison with Bernoulli sampling｜一个直接的界：与伯努利抽样比较

命题（方差的改进）

对第 43 页的单个样本 $W = 1_{{X > b}} e^{- b X + b^{2} /2}$ （在 $Q$ 下， $X \sim N (b, 1) ），$

E_{Q} W^{2} \leq e^{- b^{2} /2} p_{b}, Var_{Q} W \leq p_{b} (e^{- b^{2} /2} - p_{b}) \leq e^{- b^{2} /2} \cdot p_{b} (1 - p_{b}) .

最右边的 $p_{b} (1 - p_{b})$ 正是伯努利抽样单个样本的方差。

推导证明思路

权重有上界 $e^{- b^{2} /2} ，$ 所以 $W^{2} \leq e^{- b^{2} /2} W ；$ 取期望就把二阶矩化成一阶矩，而一阶矩已知是 $p_{b} 。$

第 1 步（上界）：由第 43 页命题第 2 条， $0 \leq W \leq e^{- b^{2} /2} 。$

第 2 步（平方 ≤ 上界 × 自己）： $W^{2} \leq e^{- b^{2} /2} W 。$

第 3 步（取期望）： $E_{Q} W^{2} \leq e^{- b^{2} /2} E_{Q} W = e^{- b^{2} /2} p_{b} 。$

第 4 步（方差）： $Var_{Q} W = E_{Q} W^{2} - p_{b}^{2} \leq e^{- b^{2} /2} p_{b} - p_{b}^{2} = p_{b} (e^{- b^{2} /2} - p_{b}) 。$

第 5 步（和伯努利比较）：要证 $p_{b} (e^{- b^{2} /2} - p_{b}) \leq e^{- b^{2} /2} p_{b} (1 - p_{b}) 。$ 两边除以 $p_{b} > 0$ 再展开，等价于

e^{- b^{2} /2} - p_{b} \leq e^{- b^{2} /2} - e^{- b^{2} /2} p_{b} ⟺ p_{b} \geq e^{- b^{2} /2} p_{b},

而 $e^{- b^{2} /2} \leq 1 ，$ 所以成立。 $■$

这个界有多准？和第 44 页的精确二阶矩对比， $b = 4$ 时直接的界是 $e^{- 8} p_{4} \approx 1.06 \times 1 0^{- 8} ，$ 精确值 $e^{16} p_{8} \approx 5.53 \times 1 0^{- 9} 。$ 只用一行推导，结果只比精确值大约 2 倍。

图解：两种方法的成本表

「10% 相对误差所需样本数」 $\approx 100 \times$ 相对方差（第 37 页）：

$b$	$p_{b}$	直接的界：至少缩小 $e^{b^{2} /2}$ 倍	精确：缩小倍数	伯努利需要	重要性抽样需要
1	$0.159$	$1.65$	$3.64$	530	146
2	$0.0228$	$7.39$	$18.4$	4296	234
3	$1.35 \times 1 0^{- 3}$	$90.0$	$218$	$7.4 \times 1 0^{4}$	339
4	$3.17 \times 1 0^{- 5}$	$2981$	$6999$	$3.2 \times 1 0^{6}$	451
5	$2.87 \times 1 0^{- 7}$	$2.68 \times 1 0^{5}$	$6.1 \times 1 0^{5}$	$3.5 \times 1 0^{8}$	568

伯努利抽样的成本约为 $\frac{100}{p _{b}} ，$ 随 $b$ 指数爆炸： $b$ 每加 1，成本涨几十到上百倍。
重要性抽样的成本每次只多一百多个样本，几乎是线性增长。
「精确」一列来自第 44 页的公式 $Var_{Q} W = e^{b^{2}} p_{2 b} - p_{b}^{2} ，$ 始终比「直接的界」好 2 倍多一点。

为什么一个指数爆炸、一个线性增长

要比较两种方法的相对方差，需要知道 $p_{b}$ 有多大。下面的 Mills 不等式给出 $p_{b}$ 的上下界（证明见本节末的「了解更多」）：

\frac{b}{1 + b ^{2}} ϕ (b) \leq p_{b} \leq \frac{ϕ ( b )}{b} (b > 0) .

例如 $b = 4 ：$ 下界 $3.15 \times 1 0^{- 5} ，$ 真值 $3.17 \times 1 0^{- 5} ，$ 上界 $3.35 \times 1 0^{- 5} ，$ 夹得很紧。

伯努利：相对方差 $\frac{1 - p _{b}}{p _{b}} \approx \frac{1}{p _{b}} \geq \frac{b}{ϕ ( b )} = 2 π b e^{b^{2} /2} ，$ 按 $e^{b^{2} /2}$ 爆炸。
重要性抽样：由命题，相对二阶矩 $\frac{E _{Q} W ^{2}}{p _{b}^{2}} \leq \frac{e ^{- b^{2} /2}}{p _{b}} 。$ 再用 Mills 下界， $ϕ (b) = \frac{e ^{- b^{2} /2}}{2 π} ，$ 所以

\frac{e ^{- b^{2} /2}}{p _{b}} \leq \frac{e ^{- b^{2} /2} ( 1 + b ^{2} )}{b ϕ ( b )} = 2 π (b + \frac{1}{b}),

只按 $b$ 线性增长。 $b = 4$ 时这个上界约 10.7，精确值（第 44 页）约 5.5。

了解更多：Mills 不等式的证明

上界： $t \geq b$ 时 $\frac{t}{b} \geq 1 ，$ 又 $ϕ^{'} (t) = - t ϕ (t) ，$ 所以

p_{b} = \int_{b}^{\infty} ϕ (t) d t \leq \int_{b}^{\infty} \frac{t}{b} ϕ (t) d t = \frac{1}{b} [- ϕ (t)]_{b}^{\infty} = \frac{ϕ ( b )}{b} .

下界：令 $g (x) = p_{x} - \frac{x}{1 + x ^{2}} ϕ (x) ，$ 其中 $p_{x} = \int_{x}^{\infty} ϕ ，$ 所以 $p_{x}^{'} = - ϕ (x) 。$ 用乘积求导和 $ϕ^{'} = - x ϕ ：$

g^{'} (x) = - ϕ (x) - \frac{1 - x ^{2}}{( 1 + x ^{2} ) ^{2}} ϕ (x) + \frac{x ^{2}}{1 + x ^{2}} ϕ (x) = - ϕ (x) [\frac{1}{1 + x ^{2}} + \frac{1 - x ^{2}}{( 1 + x ^{2} ) ^{2}}] = - \frac{2 ϕ ( x )}{( 1 + x ^{2} ) ^{2}} < 0.

（中间一步用了 $1 - \frac{x ^{2}}{1 + x ^{2}} = \frac{1}{1 + x ^{2}} ，$ 再通分 $\frac{( 1 + x ^{2} ) + ( 1 - x ^{2} )}{( 1 + x ^{2} ) ^{2}} = \frac{2}{( 1 + x ^{2} ) ^{2}} 。）$ 所以 $g$ 严格递减；又 $x \to \infty$ 时 $g (x) \to 0 ，$ 因此 $g (x) > 0 ，$ 即下界成立。

平移量取多少最好

第 44 页例 2 算出：把中心挪到 $a$ 时， $E_{Q_{a}} W_{a}^{2} = e^{a^{2}} p_{a + b} 。$ 取 $b = 4 ，$ 比较几个 $a ：$

平移量 $a$	$0$ （伯努利）	$3$	$4$ （本节的选择）	$4.12$ （最优）	$5$	$8$
$E_{Q_{a}} W_{a}^{2}$	$3.17 \times 1 0^{- 5}$	$1.04 \times 1 0^{- 8}$	$5.53 \times 1 0^{- 9}$	$5.49 \times 1 0^{- 9}$	$8.13 \times 1 0^{- 9}$	$1.11 \times 1 0^{- 5}$

$a = b$ 离最优值只差不到 1%，所以「挪到门槛上」几乎就是最好的选择。
挪得不够（ $a = 3 ）$ 或稍微过头（ $a = 5 ），$ 二阶矩大 1.5～2 倍，还能接受。
挪得太远（ $a = 8 ）$ 就糟了：比 $a = b$ 差 2000 倍，只比伯努利好 3 倍。原因是第 41 页算过的 $E_{P} L^{2} = e^{a^{2}} ：$ 平移越远，权重越不均匀，少数样本的权重主导了估计。
为什么最优值在 $b$ 附近：对 $lo g E W_{a}^{2} = a^{2} + lo g p_{a + b}$ 求导，令其为 0，得到 $2 a = \frac{ϕ ( a + b )}{p _{a + b}} 。$ 由 Mills 不等式，右边约等于 $a + b ，$ 于是 $a \approx b 。$

例子

例 1：b = 4，要 1% 的相对误差

伯努利： $n \approx \frac{1 - p _{4}}{( 0.01 ) ^{2} p _{4}} \approx \frac{1}{1 0 ^{- 4} \times 3.17 \times 1 0 ^{- 5}} \approx 3.2 \times 1 0^{8}$ 个样本。
重要性抽样： $n \approx \frac{Var _{Q} W / p _{4}^{2}}{( 0.01 ) ^{2}} = \frac{4.51}{1 0 ^{- 4}} \approx 4.5 \times 1 0^{4}$ 个样本。
差距约 7000 倍。如果每秒生成一千万个正态随机数，前者要约半分钟，后者约 5 毫秒。到 $b = 6$ （ $p_{6} \approx 9.9 \times 1 0^{- 10} ）$ 时，伯努利要约 $1 0^{13}$ 个样本，就成了真正的难题。

例 2：同样一万个样本，b = 5 时的误差

$p_{5} \approx 2.87 \times 1 0^{- 7} ，$ $n = 1 0^{4} ：$

伯努利：相对误差 $\approx \frac{1}{n p _{5}} = \frac{1}{2.87 \times 1 0 ^{- 3}} \approx 18.7 ，$ 也就是 1870%。平均命中 0.003 次，估计值几乎总是 0，完全没用。
重要性抽样：相对误差 $\approx \frac{5.68}{1 0 ^{4}} \approx 2.4% 。$

例 3：直接的界与精确值逐个对比

$b$	直接的界 $e^{- b^{2} /2} p_{b}$	精确 $e^{b^{2}} p_{2 b}$	界 ÷ 精确
1	$0.0962$	$0.0618$	$1.56$
2	$3.08 \times 1 0^{- 3}$	$1.73 \times 1 0^{- 3}$	$1.78$
3	$1.50 \times 1 0^{- 5}$	$7.99 \times 1 0^{- 6}$	$1.88$
4	$1.06 \times 1 0^{- 8}$	$5.53 \times 1 0^{- 9}$	$1.92$

比值趋于 2：Mills 近似下，直接的界约为 $\frac{e ^{- b^{2}}}{2 π b} ，$ 精确值约为 $\frac{e ^{- b^{2}}}{2 2 π b} ，$ 正好差 2 倍。损失来自第 2 步：它把 $W^{2} = W \cdot W$ 里的一个 $W$ 换成了上界 $e^{- b^{2} /2} 。$ 可是命中样本的 $W = e^{- b^{2} /2} e^{- b Z}$ 只有在恰好落在门槛上（ $Z = 0 ）$ 时才达到上界，越往右越小，所以这一步必然放大。

常见疑问与易错点

易错点问：方差缩小 7000 倍，误差也缩小 7000 倍吗？

答：不是。误差（标准差）是方差的平方根，样本数相同时误差缩小 $7000 \approx 84$ 倍。等价的说法是：同样的误差，样本数少 7000 倍。

易错点问：这个方法对任何稀有事件都这么好吗？

答：不一定。这里的事件是一条半直线 ${X > b} ，$ 「挪到门槛上」显然合理。更复杂的事件（多维、几块区域的并、路径依赖的事件）中，找好的 $Q$ 本身就是难题。选错了，方差可能比伯努利还大，甚至无穷（第 36 页、第 38 页的教训；上表 $a = 8$ 也已经很差）。

易错点问：直接的界和精确值只差 2 倍，为什么还要算精确值？

答：直接的界适合快速判断「量级」和「趋势」（指数 vs 线性）；精确值用来做精细的比较，例如判断平移量取 4 还是 4.12。两者各有用处，这也是课件把它们分成两页的原因。

小结与自测

小结本页小结

直接的界： $0 \leq W \leq e^{- b^{2} /2}$ ⇒ $E_{Q} W^{2} \leq e^{- b^{2} /2} p_{b}$ ⇒ $Var_{Q} W \leq e^{- b^{2} /2} \cdot p_{b} (1 - p_{b}) 。$
与伯努利抽样比，方差至少缩小 $e^{b^{2} /2}$ 倍： $b = 4$ 时约 2981 倍，精确约 7000 倍。
相对方差：伯努利约 $\frac{1}{p _{b}} ，$ 按指数爆炸；重要性抽样 $\leq 2 π (b + \frac{1}{b}) ，$ 按线性增长。
平移量 $a = b$ 几乎最优；挪得太远会让权重极不均匀。

小结第 5 部分串起来

第 36 页：最朴素的抽样无偏，方差却可能无穷。
第 37 页：误差由 $\frac{σ ^{2}}{n}$ 决定，所以方差就是成本。
第 38 页–第 40 页：在 $(0, 1)$ 上换一个抽样密度，抵消奇点，让方差变有限。
第 41 页–第 42 页：高斯换测度 $e^{a X - a^{2} /2} ，$ 以及两次平移的复合。
第 43 页–第 45 页：用它估计稀有事件 $P (X > b) ，$ 方差缩小 $e^{b^{2} /2}$ 倍以上。

自测

1. $b = 3$ 时，直接的界保证方差至少缩小多少倍？精确值是多少？

点开看答案

至少 $e^{b^{2} /2} = e^{4.5} \approx 90$ 倍；精确值约 218 倍（见成本表）。

2. 证明：若 $0 \leq W \leq c ，$ 则 $Var W \leq c E W - (E W)^{2} 。$

点开看答案

$W^{2} = W \cdot W \leq c W$ （ $W \geq 0 ），$ 取期望得 $E W^{2} \leq c E W ，$ 所以 $Var W = E W^{2} - (E W)^{2} \leq c E W - (E W)^{2} 。$

3. 用 Mills 上界 $p_{b} \leq \frac{ϕ ( b )}{b}$ 估计 $p_{6} ，$ 并与真值 $9.87 \times 1 0^{- 10}$ 比较。

点开看答案

$ϕ (6) = \frac{e ^{- 18}}{2 π} \approx \frac{1.523 \times 1 0 ^{- 8}}{2.5066} \approx 6.08 \times 1 0^{- 9} ，$ 除以 6 得约 $1.01 \times 1 0^{- 9} ，$ 只比真值大约 2.6%。 $b$ 越大，Mills 上界越准。

本页术语中英对照（按出现顺序）

中文	English	白话解释
方差	variance	Var X = E[(X − E X)²]，衡量随机变量围绕均值的波动大小。
事件	event	样本空间的（允许谈概率的）子集；实现的 ω 落在里面，就说事件发生。
重要性抽样	importance sampling	从另一个更合适的分布抽样，再乘以权重纠正，从而减小估计的方差。
期望	expectation	随机变量对概率测度的积分 E[X] = ∫ X dP，也就是「加权平均」。
上界	upper bound	数集 A 的上界是一个数 M，A 里每个数都 ≤ M。例如 2 和 5 都是 [0,1] 的上界；所有上界中最小的那个叫上确界。
阶矩	moment	E[\|X\|ᵖ] 叫 p 阶（绝对）矩；它有限与否反映尾部有多「重」。
下界	lower bound	数集 A 的下界是一个数 m，A 里每个数都 ≥ m。例如 0 和 −3 都是 (0,1] 的下界；所有下界中最大的那个叫下确界。
换测度	change of measure	用 E_Q[X] = E_P[X · dQ/dP] 在两个概率之间换算期望。