Acceptance-Rejection Method Acceptance Probability Proof

Question

I did not fully understand the proof of the acceptance probability.

The acceptance-rejection algorithm is described as follows:

• suppose you have RVs $X$ and $Y$ with densities $f$ and $g$, respectively, and there exists a constant $c$ such that $\frac{f(t)}{g(t)} \leq c$ for all $t$ such that $f(t) > 0$, then
  1. generate random $y$ from distribution with density $g$
  2. generate random $u$ from $\text{Uniform}(0, 1)$
  3. if $u < \frac{f(y)}{cg(y)}$ accept $y$ and deliver $x = y$, otherwise repeat

In Rizzo's book 'Statistical Computing with R' (p56) he writes

$P(\text{accept}|Y)=P(U<\frac{f(Y)}{cg(Y)}|Y)=\frac{f(Y)}{cg(Y)}$

and so

$\sum_y{P(\text{accept}|y)P(Y=y)}=\sum_y{\frac{f(y)}{cg(y)}g(y)}=\frac{1}{c}$

This still makes sense to me, but what about the continuous version of this proof, which is as follows:

$ \begin{aligned} P(A) =& \int_{-\infty}^{\infty}dy\int_0^{\frac{f(y)}{cg(y)}}g(y)du \\ =& \int_{-\infty}^{\infty}\frac{1}{c}f(y)dy \\ =& \frac{1}{c}. \end{aligned} $

Could someone explain to me specifically how you get to this double integral?

Answer 1

If you target $f$ with $g$, and you know $f(x) \le g(x)c$, then \begin{align*} P(\text{accept proposal}) &= P\left( U \le \frac{f(X)}{g(X)c} \right) \\ &= E\left( \mathbf{1}\left[U \le \frac{f(X)}{g(X)c}\right] \right) \tag{*}\\ &= E\left( E\left[ \mathbf{1}\left\{U \le \frac{f(X)}{g(X)c}\right\} \bigg\rvert X \right]\right) \\ &= E\left( P\left[ U \le \frac{f(X)}{g(X)c} \bigg\rvert X \right]\right) \\ &= E\left( \frac{f(X)}{g(X)c} \right) \\ &= c^{-1}\int f(x)g(x)/g(x) \text{d}x \\ &= c^{-1}. \end{align*}

Note that (*) is a double integral because both $U$ and $X$ are random, so you must integrate their joint density over the appropriate region. They are independent, so their joint density factors, so the joint density is $f_U(u)g_X(x) = 1 \cdot g(x) = g(x)$. There is no $u$ in this expression because it is a uniform random variable--just make sure you integrate over the right bounds.