Past exam of the Probability, statistics and options II course of the University of Oxford / 2010 / S / S2 / a

Independently draw $Y\sim q$ and $U\sim \mathrm{Uniform}(0,1)$. Accept $Y$ if $U\le p(Y)/(Mq(Y))$; otherwise discard it and repeat with fresh independent draws. Return the first accepted value. The bound makes the acceptance probability at each proposal at most one. As $\int p=1$, the total acceptance probability is $1/M>0$, so the procedure terminates almost surely. Values outside the proposal support must have target density zero for the stated envelope assumption to make sense.

For one trial and any measurable set $A$,Since the acceptance probability is $1/M$, conditioning gives target probability ${\int }_{A}p$. Repeating failed independent trials does not alter this conditional law: summing over the trial number multiplies by the geometric sum ${\sum }_{j\ge 0}(1-1/M{)}^j/M=1$. Taking $A=(-\infty ,x)$ proves