3
$\begingroup$

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?

$\endgroup$
  • 4
    $\begingroup$ By not explaining the notation you are making your readers work harder than they need to, so consider describing the meanings of $f$, $g$, and $A.$ As far as the double integral goes, your understanding might benefit from a method that almost always helps: draw a picture of the region it describes. $\endgroup$ – whuber Sep 7 '18 at 23:31
5
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Correct though your answer is, I think the OP's question is really about where the double integral in the first line of $P(A) = \dots$ comes from and how it works to get to the final result, not about the broader move from summation to integration. $\endgroup$ – jbowman Sep 8 '18 at 1:52
  • $\begingroup$ @jbowman ah that's right. I went a little quick. Hopefully this change takes care of that. I also thought that that first line of OP's was just a mistake, but now I see I've clarified it for the both of us. $\endgroup$ – Taylor Sep 8 '18 at 2:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.