我们用一个具体的数学例子来说明拒绝采样的工作原理。
问题描述：
假设我们想要从一个复杂的概率分布 p(x) 中生成样本，但这个分布难以直接采样。我们选择一个简单的分布 q(x) （比如均匀分布或正态分布），并且已知 p(x) \leq M \cdot q(x) ，其中 M 是一个常数。
例子：
假设目标分布 p(x) 是一个截断的指数分布，定义在区间 [0, 1] 上：
[
p(x) = \frac{e^{-x}}{\int_0^1 e^{-t} dt} = \frac{e^{-x}}{1 - e^{-1}}, \quad x \in [0, 1]
]
这个分布难以直接采样，因此我们选择一个简单的分布 q(x) —— 均匀分布：
[
q(x) = 1, \quad x \in [0, 1]
]
我们需要找到一个常数 M ，使得 p(x) \leq M \cdot q(x) 对所有 x \in [0, 1] 成立。观察到 p(x) 在 x=0 时取得最大值：
[
p(0) = \frac{1}{1 - e^{-1}} \approx 1.582
]
因此，我们可以选择 M = 1.582 。
拒绝采样的步骤：
从简单分布 q(x) 中生成一个样本 x ：
从均匀分布 U(0, 1) 中生成一个随机数 x 。
计算接受概率 \alpha(x) ：
[
\alpha(x) = \frac{p(x)}{M \cdot q(x)} = \frac{e^{-x}}{1 - e^{-1}} \cdot \frac{1}{1.582}
]
这里 M \cdot q(x) = 1.582 。
生成一个均匀随机数 u \in [0, 1] ：
从均匀分布 U(0, 1) 中生成另一个随机数 u 。
决定是否接受样本 x ：
- 如果 u \leq \alpha(x) ，则接受 x 作为目标分布 p(x) 的样本。
- 否则，拒绝 x ，重新生成样本。
具体实现（伪代码）：
import numpy as np
# 定义目标分布 p(x) 和常数 M
def p(x):
return np.exp(-x) / (1 - np.exp(-1))
M = 1.582
# 拒绝采样
def rejection_sampling():
while True:
x = np.random.uniform(0, 1) # 从简单分布 q(x) 生成样本
u = np.random.uniform(0, 1) # 生成均匀随机数
alpha = p(x) / (M * 1) # 计算接受概率
if u <= alpha:
return x # 接受样本
# 生成 1000 个样本
samples = [rejection_sampling() for _ in range(1000)]
结果：
通过上述方法，我们可以生成符合目标分布 p(x) 的样本。这些样本的分布会逐渐逼近目标分布 p(x) 。
关键点：
- 简单分布 q(x) ：必须能够覆盖目标分布 p(x) 的支持区域（这里是 [0, 1]）。
- 常数 M ：需要确保 p(x) \leq M \cdot q(x) 对所有 x 成立。
- 效率：接受概率 \alpha(x) 越高，采样效率越高。如果 M 过大，会导致大量样本被拒绝，效率降低。
这个例子清晰地展示了拒绝采样的数学原理和实现过程！
