= Solution
For one proposal, $P(Y=x,\text{accept})=q(x)\tilde p(x)/(M\tilde q(x))=\tilde p(x)/(MZ_q)$. Summing gives total acceptance probability $a=Z_p/(MZ_q)>0$. Conditioning on acceptance therefore gives $P(Y=x\mid\text{accept})=\tilde p(x)/Z_p=p(x)$.
The first accepted result has this law too: the probability of $k-1$ failures followed by acceptance at $x$ is $(1-a)^{k-1}\tilde p(x)/(MZ_q)$. Sum the <geometric series> over $k\ge1$ to obtain $\boxed{P(X=x)=p(x)}$. Positive acceptance probability also proves almost-sure termination.
Back to article page
