= Solution
Write $C=\int_{\mathbb R}f(x)\,dx$, so $0<C<\infty$. The finite envelope condition means that $f\leq Mg$ almost everywhere; in particular, the proposal must cover the support of the target.
For each <independent> proposal $Y\sim g$, generate an <independent> $U\sim\operatorname{Unif}(0,1)$ and accept $Y$ precisely when
$$
\boxed{U\leq\frac{f(Y)}{Mg(Y)}.}
$$
Discard a rejected proposal and continue. The ratio is in $[0,1]$ and is needed only where $g(Y)>0$. Neither evaluation of $C$ nor prior knowledge of the normalized target is required.
To prove the output law, for any measurable set $D$ the joint <probability> of acceptance and a proposal in $D$ is
$$
\mathbb P(Y\in D,\mathrm{accept})
=\int_Dg(y)\frac{f(y)}{Mg(y)}\,dy
=\frac1M\int_Df(y)\,dy.
$$
Dividing by the total acceptance <probability> $C/M$ gives $\int_D f(y)/C\,dy$, the target <probability>. <Independent> proposal-uniform pairs give <independent> accepted observations. With a finite proposal list there can be no accepted value; with continued <independent> trials, acceptance eventually occurs almost surely because $C/M>0$.
Back to article page
