接受-拒绝技术定理证明

机器算法验证 可能性 模拟 概率规划
2022-04-07 13:15:29

我被指派在我们班讨论接受-拒绝技巧。我很难理解证明其定理的最后一部分。

定理是这样的:

接受-拒绝算法生成一个随机变量 X 使得P{X=j}=pj,j=0,1...

另外,需要得到算法的迭代次数X是具有均值的几何随机变量c.

证明是这样的:

在此处输入图像描述

(我不是很擅长,所以我只是附上一张照片)

我不太明白它是怎么转的1/c接着pj在证明的最后两部分。

1个回答

提案被接受的概率是总和j这就是价值j是(1)生成然后(2)接受:

P(proposal accepted)=j=1P(proposal accepted and Y=j)=j=1P(proposal accepted |Y=j)P(Y=j)=j=1pjc=1cj=1pj=1c
(在考虑连续密度时,这个论点要直截了当,因为它对应于面积比,1在目标下与c根据提案。下图取自我们的蒙特卡洛书。)

在此处输入图像描述

接受值等于的概率j是一个值的概率j被提议并被接受除以一个值被接受的概率:

P(X=j)=P(Y=j|Y is accepted)=P(Y=j is accepted)P(proposal is accepted)=pj/c1/c=pj