Past exam of the Probability, statistics and options II course of the University of Oxford / 2009 / S / S2 / b / Solution

For one proposal, $P(Y=x,\text{accept})=q(x)\tilde{p}(x)/(M\tilde{q}(x))=\tilde{p}(x)/(M{Z}_q)$. Summing gives total acceptance probability $a=Z_p/(M{Z}_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)/(M{Z}_q)$. Sum the geometric series over $k\ge 1$ to obtain $\boxed{P(X=x)=p(x)}$. Positive acceptance probability also proves almost-sure termination.