Understanding the acceptance-rejection method

Question

Today in my class the acceptance-rejection method, used to simulate draws from a certain distribution, was explained as follows:

I thought I understood the acceptance-rejection method, but looking at this slide I now know that I don't understand it at all.

Question:

• First of all, why does this method work? Looking at the density function $f$, you would want most of the draws to lie in the interval $[0.4,0.8]$. However, $f$ is large for $x\in[0.4,0.8]$, which means that values in $[0.4,0.8]$ are less likely to be accepted than values in $[0,0.4]$. I understand that this is a good thing if you're sampling from a proposal distribution where the the density function is not equal to $f(x)\neq 1$, since you would want outliers to be accepted with a high probability because they get simulated less often. In this case though, we're just drawing $U_1$ from the uniform distribution, so small values will be drawn just as often as larger values.

• What is meant with $P(X\in dx)$, the probability that $X$ is in the infinitely small interval $[x,x+dx]$? Why are we looking at $dx$? I don't understand what the small interval $dx$ is doing in this picture. Similarly, I don't understand why we're looking at $P(U_1\in dx, \text{ accept})$ and why this would be equal to $f(x)dx/c$. Why aren't we just looking at $P(U_1 \text{ accepted})$?

Thanks!

PS: I understand that this question is suitable for Cross Validated as well, but I feel that my misunderstanding is related to probability theory more than it is to simulation.

Answer 1

For your first bullet, you are correct that there is a typo in the book. You should accept the point if $U_2 \le f(U_1)$. That accepts more points where $f(x)$ is high and few points where $f(x)$ is low.

For the second, we cannot ask the probability that an accepted point has value exactly $x$ because you will choose any particular value with probability $0$. We can ask what is the probability the accepted point is in the range $[x,x+dx]$ because that represents an (infinitesimal) area of the box so there is a(n infinitesimal) probability that the point is inside.