重要性抽样

重要性抽样（importance sampling）通过改变抽样分布，并给每个样本乘上相应的概率或密度比，估计目标分布下的期望。它把计算次数更多地放在对积分有贡献的区域，常用于概率计算、模拟和贝叶斯积分。改变抽样分布后直接数频率，得到的是新分布的结果；权重负责把结果换回目标分布。

以四次独立的公平硬币试验为例，令K为正面次数，目标是求至少三次正面的概率。按二项分布，精确答案为 $(4+1)/16=5/16$。这个小例子可以直接算完，用来逐项检查抽样和加权；同样的思想可用于无法枚举的大系统。

让目标事件更常发生

若模拟时把每次正面的概率从二分之一改成四分之三，K≥3会更常出现。但这时直接频率趋向 $$\underset{q}{Pr}(K\ge 3)=4(3/4{)}^3(1/4)+(3/4{)}^4=189/256,$$ 远大于目标 $5/16$。下标q提醒这里已经换了分布。

对某一条具体的四次结果序列，若有k次正面，其目标概率为 $p(x)=1/16$，提议概率为 $q(x)=(3/4{)}^k(1/4{)}^{4-k}$，所以权重为 $$w(x)=\frac{p(x)}{q(x)}=\frac{16}{3^k}.$$ 三次正面的每个样本给事件概率估计贡献 $16/27$，四次正面贡献 $16/81$；不到三次贡献零。较常被模拟出来的结果，单次贡献相应变小。

横轴为K。金色提议分布把更多概率放在3与4，估计公平硬币的概率时必须按各K的概率比校正。

换分布恒等式与无偏性

设目标密度p与提议密度q相对于同一参考测度定义，待估量为 $\mu =\int h(x)p(x)\mathrm{d}x$，并假设 $\int |h|p<\mathrm{\infty }$。若在 $h(x)p(x)\ne 0$ 的区域内q几乎处处为正，则 $$\mu =\int h(x)\frac{p(x)}{q(x)}q(x)\mathrm{d}x={𝔼}_q[h(X)w(X)].$$ 在q为零、且 $hp=0$ 的地方，乘积贡献约定为零。离散分布把积分改为求和，同一推导仍成立。抽取独立同分布的 $X_1,\dots ,X_N\sim q$，得到 $${\hat{\mu }}_N=\frac{1}{N}\sum _{i=1}^{N}h(X_i)w(X_i),{𝔼}_q{\hat{\mu }}_N=\mu .$$ 可积性保证上述无偏性，也允许应用独立样本的强大数定律得到一致性。若再有 $\int h^2{p}^2/q<\mathrm{\infty }$，独立性给出 $${\mathrm{Var}}_q({\hat{\mu }}_N)=\frac{1}{N}[\int \frac{h(x{)}^{2}p(x{)}^2}{q(x)}\mathrm{d}x-{\mu }^2].$$ 因此，提议分布是否改善计算，要看这个二阶积分及生成样本的成本，不能只看目标事件出现得是否更多。

四次试验的完整方差计算

对开头的事件取 $h(x)={\mathrm{𝟏}}_{\{K\ge 3\}}$。在q下，K=3与K=4的概率分别为 $27/64$、$81/256$。一次加权贡献Y的均值为 $$𝔼Y=\frac{27}{64}\frac{16}{27}+\frac{81}{256}\frac{16}{81}=\frac{1}{4}+\frac{1}{16}=\frac{5}{16}.$$ 二阶矩和方差分别为 $$𝔼Y^2=\frac{27}{64}{\left(\frac{16}{27}\right)}^2+\frac{81}{256}{\left(\frac{16}{81}\right)}^2=\frac{13}{81},$$ $$\mathrm{Var}(Y)=\frac{13}{81}-\frac{25}{256}=\frac{1303}{20736}\approx \mathrm{0.062838.}$$ 直接模拟公平硬币时，单次贡献是成功概率 $5/16$ 的0或1，方差为 $(5/16)(11/16)=55/256\approx 0.214844$。在同样N次四硬币模拟下，两种均值估计的方差之比约为0.2925；这项收益已经包含加权后的波动，而不是只比较成功次数。

将提议的正面概率记为一般的 $r\in (0,1)$，逐条对四个三正面序列和一个四正面序列求和，可得一次贡献的二阶矩 $$M(r)=\frac{1}{64r^3(1-r)}+\frac{1}{256r^4}.$$ 若r过小，目标事件罕见，偶尔出现时权重很大；若r过于接近一，四正面虽常出现，三正面的提议概率却趋近零，第一项又会发散。增加事件出现概率并不等同于降低估计方差。

纵轴采用对数刻度。金色虚线是直接模拟的方差55/256；圆点标出r=3/4。

直接运行的加权模拟

代码专门计算本篇的四次试验事件。为避免把极端权重的溢出混入教学，提议参数限定在 $0.05\le r\le 0.95$；这只是此实现的范围，数学恒等式允许更广的提议分布。返回加权均值及其独立样本标准误估计。

Python 3

import math
import random

def four_coin_importance(n, r=0.75, seed=26):
    if type(n) is not int or n < 2:
        raise ValueError("at least two simulations required")
    if not math.isfinite(r) or not 0.05 <= r <= 0.95:
        raise ValueError("this example requires 0.05 <= r <= 0.95")
    rng = random.Random(seed)
    mean, m2 = 0.0, 0.0
    for i in range(1, n + 1):
        k = sum(rng.random() < r for _ in range(4))
        contribution = 0.0
        if k >= 3:
            proposal = r ** k * (1 - r) ** (4 - k)
            contribution = (1 / 16) / proposal
        delta = contribution - mean
        mean += delta / i
        m2 += delta * (contribution - mean)
    standard_error = math.sqrt(m2 / (n - 1) / n)
    return mean, standard_error

print(four_coin_importance(20000))
print("exact probability:", 5 / 16)

循环中每次更新均值和离差平方和，不存储全部样本；时间为 $O(N)$、额外空间为 $O(1)$。返回的标准误也是随机估计，尤其不能把一次运行中的小标准误视为支撑与尾部条件已被验证。若使用相关的链样本，需要另做相关误差分析。

未知归一化常数与使用边界

若只知道 $p(x)=\tilde{p}(x)/Z$，Z未知，不能直接把 $\tilde{p}/q$ 当作已归一化权重代入无偏估计式。常用的自归一化重要性抽样是 $${\tilde{\mu }}_N=\frac{\sum _{i}h(X_i){\tilde{w}}_i}{\sum _i{\tilde{w}}_i},{\tilde{w}}_i=\frac{\tilde{p}(X_i)}{q(X_i)}.$$ 这里需要比普通估计式更强的支撑条件：在整个p为正的区域，q都应几乎处处为正。再假设 $0<Z<\mathrm{\infty }$、$\int |h|p<\mathrm{\infty }$，则分母样本平均趋向Z，分子样本平均趋向Zμ，故在分母非零时可计算的比值估计一致；有限样本下一般有偏，因为期望不能穿过一个随机比值。

例如目标在0、1各放二分之一概率，只想计算取值为1的概率。若提议只产生1，普通加权贡献恒为二分之一，仍准确覆盖了本积分的非零部分；但把同样的权重再作自归一化，分子与分母完全相同，结果恒为一。问题在于分母没有覆盖整个目标分布，不能恢复归一化常数。

变式。 在硬币例中将r设为1，只会模拟到四正面。即使对这个结果乘上目标概率 $1/16$，仍永远不会看到三正面的四条序列，平均只能得到 $1/16$。丢失的 $1/4$ 正是提议支撑未覆盖的贡献。相反，若取r=1/2，权重恒为一，方法退回直接模拟，其方差就恢复为 $55/256$。

拒绝抽样保留或丢弃候选并产生目标样本；重要性抽样保留提议样本，通过权重估计目标积分。加权样本本身并未因此变成独立的目标分布样本。

参考资料

• Marina Meila：STAT 403，Lecture III — Importance sampling and rejection sampling，第3—5页，恒等式与方差。本文的四硬币算例及方差曲线为独立构造。