本文会介绍拒绝采样的工作流程和原理。

Workflow

在计算机中，可以通过均匀分布来实现常用的Gaussian，gamma等等分布，但是怎么从任意一个给定概率密度函数的分布中采样呢？

拒绝性采样就是解决上述问题的一种方法。对于给定的概率密度函数， $f(y)$ ，通过一个计算机已经实现的分布， $g(y)$ ，例如正态分布，和常数 $c$ 来进行如下采样：

从均匀分布 $\rm U(0,1)$ 中采样，得到 $p$ ；
从分布 $g(y)$ 中采样得到点 $y$ ；
计算 $\alpha = \frac{f(y)}{c g(y)}$ ，当 $p \leq \alpha$ 时，把点 $y$ 当作从 $f(y)$ 分布中采集的样本点。

常数 $c$ 需要满足

\begin{aligned} c \geq \max \frac{f(y)}{g(y)} \end{aligned}

Theorem

下面证明上述方法的有效性。

令 $F(y)$ 和 $G(y)$ 分别表示累计概率分布函数，我们要证明

\begin{aligned} F(y) = P(Y\leq y \vert U\leq \frac{f(y)}{c g(y)}) \end{aligned}

上式中，左边是 $y$ 从 $f(y)$ 中采样对应的累计概率分布，右边的 $y$ 是我们从 $g(y)$ 中采样得到的条件累计概率分布。一定要分清 $y$ 的来自哪个分布。

通过贝叶斯公式得到

\begin{aligned} P(Y\leq y \vert U\leq \frac{f(y)}{c g(y)}) &= \frac{P(U\leq \frac{f(y)}{c g(y)}\vert Y\leq y)P(Y\leq y)}{P(U\leq \frac{f(y)}{c g(y)})} \end{aligned}

对于分母，

\begin{aligned} P(U\leq \frac{f(y)}{c g(y)}) &= \int P(U\leq \frac{f(y)}{c g(y)}\vert Y=y) P(Y=y) \\ &= \int \frac{f(y)}{c g(y)} g(y)\, dy\\ &= \frac{1}{c}. \end{aligned}

对于分子的第一项

\begin{aligned} P(U\leq \frac{f(y)}{c g(y)}\vert Y\leq y) &= \frac{\int^y_{-\infty} P(U\leq \frac{f(y)}{c g(y)}\vert Y=y) P(Y=y)}{P(Y\leq y)}\\ &= \frac{\int_{-\infty}^y \frac{f(y)}{c g(y)} g(y) \, dy}{G(y)}\\ &= \frac{F(y)}{cG(y)} \end{aligned}

结合分子的第二项，即 $G(y)$ ，我们可以得到分子的结果为 $\frac{F(y)}{c}$ 。

因此可知，

\begin{aligned} F(y) = P(Y\leq y \vert U\leq \frac{f(y)}{c g(y)}) \end{aligned}

即按照上述流程得到的 $y$ 等价于从 $f(y)$ 中采样。