= Solution
For <rejection sampling>, independently generate a proposal $Y$ with density $g$ and a uniform $U$ on $(0,1)$. Accept $Y$ if $U\le f(Y)/(Mg(Y))$; otherwise generate a fresh independent pair and repeat. Set the ratio to zero on $g=0$ where necessarily $f=0$. The envelope condition makes the acceptance threshold at most one.
For any measurable set $A$, a single attempt satisfies
$$
\mathbb P(Y\in A,\text{ accepted})=\int_Ag(y)\frac{f(y)}{Mg(y)}dy
=\frac1M\int_Af(y)dy.
$$
Taking the whole space shows that acceptance has probability $1/M$. Conditioning on acceptance therefore gives density $f$. Repeating rejected independent attempts preserves that conditional law and terminates almost surely; the number of attempts is geometric with mean $M$.
For fixed proposal density, admissibility requires $M\ge\sup_{g(x)>0}f(x)/g(x)$ under the pointwise convention in the question. Since $1/M$ decreases with $M$, \b[the smallest valid envelope gives the greatest acceptance probability]:
$$
\boxed{M_* =\sup_{g(x)>0}\frac{f(x)}{g(x)},\qquad p_{\mathrm{acc}}=1/M_*.}
$$
For densities specified only almost everywhere, replace the supremum by the essential supremum. Integration of the envelope also gives $M\ge1$.
Back to article page
