Past exam of the mathematics course of the University of Cambridge / 2014 / iii / Paper 36 / 4 / b / Solution

For each proposal $X\sim g$, independently draw $U\sim \mathrm{Unif}(0,1)$ and accept it whenThe ratio is at most one, as required. For any measurable set $A$,so the acceptance probability is $p=1/M$ and the conditional distribution of an accepted proposal has density $f$. Repeating independent trials until acceptance therefore gives an exact draw from $f$, and repeating the whole procedure gives iid target draws. This proves rejection sampling.

The number of proposals for one successful draw is geometric with mean $M$. Thus $M$ is also the expected proposal cost of this exact simulation method.