= Solution
For each proposal $X\sim g$, independently draw $U\sim\operatorname{Unif}(0,1)$ and accept it when
$$
\boxed{U\leq\frac{f(X)}{Mg(X)}.}
$$
The ratio is at most one, as required. For any measurable set $A$,
$$
\mathbb P(X\in A,\text{accept})=\frac1M\int_Af(x)\,dx,
$$
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.
Back to article page
