拒绝采样

拒绝采样 (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 或重要性采样。

检验攻克程度：针对「拒绝采样」专属刷题排雷

做单选排雷题、推导选项机制，答错自动收录进专属错题本。