= Solution
Integrating the envelope $p\leq Mq$ shows $M\geq1$. One trial of <rejection sampling> draws $Y\sim q$ and an <independent> $U$ from the <uniform distribution> on $(0,1)$, and accepts $Y$ if $U\leq p(Y)/(Mq(Y))$. Repeat with fresh <independent random variables> after each rejection. Ratios need only be evaluated where $q>0$; the envelope makes the target zero wherever $q=0$.
For any <measurable set> $B$, integration of the <conditional probability> of acceptance gives
$$
\mathbb P(Y\in B,\mathrm{accept})=\int_Bq(y)\frac{p(y)}{Mq(y)}\,dy=\frac1M\int_Bp(y)\,dy.
$$
Taking the whole domain gives acceptance <probability> $1/M$, and dividing gives $\mathbb P(Y\in B\mid\mathrm{accept})=\int_Bp(y)\,dy$. Fresh trials therefore supply <independent and identically distributed random variables> $X_1,\ldots,X_m$ with target <probability density function> $p$. The corresponding <Monte Carlo estimator> is
$$
\boxed{\widehat\theta_m^{\mathrm{RS}}=\frac1m\sum_{j=1}^m\phi(X_j).}
$$
The proposal count $T$ up to and including one acceptance has the <geometric distribution>
$$
\mathbb P(T=t)=(1-1/M)^{t-1}/M,\quad t=1,2,\ldots,
\qquad
\boxed{\mathbb ET=M.}
$$
For example, the <tail-sum formula> gives $\mathbb ET=\sum_{t\geq0}(1-1/M)^t=M$. Thus the expected cost is $M$ proposal draws per accepted target draw.
Back to article page
