接受拒绝采样

采样

所谓采样，就是已知某个分布的概率密度函数，指按照某种方法获取一些样本，使得这些样本服从这个分布。先从最简单的离散的分布来考虑。假设$X$服从以下分布：

X	0	1
P	0.6	0.4

即$X$有$0.6$的概率会取到$0$，$0.4$的概率会取到$1$。我们可以利用轮盘赌选择法来进行采样。即按均匀分布随机产生$[0,1]$间的数字$k$（假定均匀分布的采样是可行的），如果$k$落在区间 $[0,0,4)$中，则选取样本$0$，如果落在$[0.4,1]$，则选取样本$1$。我们重复以上操作即可得到服从上述分布的样本。

连续分布的采样

对于连续的分布，我们也可以利用上述思想。假设已知某个分布的概率密度函数为$p(x)$，可以计算其分布函数$F(x)=\int_{-\infty}^xp(t)\text{d}t$。由于分布函数的取值范围是$[0,1]$，所以可以在$[0,1]$间均匀采样得到$k$，然后选取取值为$F^{-1}(k)$的样本。其中$F^{-1}(x)$是$F(x)$的反函数，由于$F(x)$单调递增，因此$F^{-1}(x)$一定存在。

连续分布的采样遇到的问题

如果按照上述方法进行采样，我们就必须根据概率密度函数$p(x)$去计算分布函数$F(x)=\int_{-\infty}^xp(t)\text{d}t$。然而当$p(x)$很复杂时，求积分的过程可能会十分困难。为了解决这个问题，可以利用接受拒绝采样的方法。

接受拒绝采样

接受拒绝采样的思想是，找一个辅助分布$Q$，设其概率密度函数为$q(x)$，它的分布函数易于求得。利用这个易于求得的分布函数去采样得到样本，并根据一些条件去选择是否保留（即接受或拒绝）该样本。所以说，接受拒绝采样的关键是找到一个标准，使得在辅助分布函数中采样得到的样本因为这个标准的限制而满足所要采样的分布。

接受拒绝采样的流程

1. 假设要采样的分布的概率密度函数为$p(x)$；
2. 选择一个辅助分布函数$Q$，设其概率密度函数为$q(x)$，通常可选均匀分布或高斯分布；
3. 选择一个常数$c$，使得$p(x)\leq cq(x)$（c最好接近于1）；
4. 从分布$Q$采样，得到样本$y$；
5. 从均匀分布$U(0,1)$采样，得到$u$；
6. 如果$u\leq \frac{f(y)}{c q(y)}$则接受样本y，否则拒绝；
7. 重复上述过程4-6直至满足条件。

上述第6步即为我们提供了一个接受拒绝的标准，类似于轮盘赌选择法，在$[0,cq(y)]$中随机选择一个点，如果该点落入$[0,f(y)]$中我们就接受样本，否则拒绝。可以看出，$p(x)$越接近$cq(x)$，则接受样本的概率越大。这也是第3步选取常数$c$以及$c$最好接近于1的原因。

接受拒绝采样的缺点

接受拒绝采样必须依赖一个辅助分布，然而如果这个分布选取的不合适那么将导致所采样的样本大概率会被拒绝，使得采样的效率大大降低。