拒绝采样

拒绝采样 (Rejection Sampling) 从难以直接采样的目标分布 $p(x)$ 生成分布严格正确的样本:选一个易采样的提议分布 $q(x)$,取常数 $M$ 使 $p(x) \le M q(x)$ 处处成立(包络条件)。算法循环:采样 $X \sim q$,再采样 $U \sim \text{Uniform}(0, 1)$,若 $U \le p(X)/(M q(X))$ 则接受 $X$,否则重试。接受概率推导:

其中积分前的 $q(x)$ 是 $X$ 取到 $x$ 的密度,括号内是该点被接受的条件概率;期望重试次数恰为 $M$ — 包络越紧($M$ 越接近 1)效率越高,且结果与 $p$ 的归一化常数无关($p$ 可差常数倍,被 $M$ 吸收进包络)。

目标分布只有未归一化形式(如贝叶斯后验 $\propto$ 先验 $\times$ 似然)且维度低时;面试常考接受率推导与“为什么高维失效”。

不需求 $F^{-1}$、不需求归一化常数,即可得到精确样本,是精确采样中最简单通用的一族;但接受率 $1/M$ 在 $d$ 维空间随体积集中按指数恶化($M \propto c^d$),高维下几乎全部被拒,必须转向 MCMC 或重要性采样。

推导拒绝采样的接受概率 $P(\text{accept}) = 1/M$,说明它为何与 $p$ 的归一化常数无关?

拒绝采样的完整算法流程是什么?期望重试次数与 $M$ 的关系?

为什么拒绝采样在高维会失效?(体积集中、包络常数指数增长的直觉)

如何选择好的提议分布 $q$ 与常数 $M$?包络过松会付出什么代价?

拒绝采样能处理未归一化的 $p$ 吗?如何修改使 $p$ 可差一个常数倍?