I understand how Accept/Reject sampling works, but sometimes I see graphical representations like this one:
Here we have the sample distribution above the target distribution. Then at a certain x-value, a vertical line is drawn where the space between the 2 distributions is marked as "reject", and the space below the target distribution is marked as "accept". But what does the red part of the line even mean? Why is this a correct visual representation of the method?
This graphical representation is the key to why rejection sampling works so it's good to test your understanding of the mathematics through it.
The setting is as follows: we have a probability distribution $p(x)$ that is difficult to sample from. However, the unnormalized $\tilde{p}(x) =Zp(x)$ for some possibly unknown Z is easy to evaluate.
We first come up with a simpler proposal distribution $q(x)$, such as a Gaussian from which we can easily draw samples. Then, we find an upper bound $kq(x) \ge \tilde{p}(x)$ so that the proposal distribution envelops the one we want to sample from.
So far, we have the following elements of the graphical representation: the blue-line target is $\tilde{p(x)}$ and the dashed-line envelope is $kq(x)$.
The algorithm starts by generating some $x_0 \sim q(x)$ from the proposal distribution. In the plot, $x_0 = 2$.
We now generate a different sample $y_0 \sim U[0, kq(x_0)]$, which lies somewhere between 0 and the proposal distribution on the y-axis at $x_0$.
The pair $(x_0, y_0)$ has a uniform distribution under the curve $kq(x)$. We need a way to filter such pairs so that in the end, the remaining ones have uniform distribution under the curve $\tilde{p}(x)$ instead. So we do the following:
If $y_0$ lies below the target distribution, that is, if $y_0 < \tilde{p}(x_0)$ then it can be considered a sample from $\tilde{p}(x)$ and be accepted, even though it was generated through $q(x)$. That is what the green line represents.
If however it is above the target, it should be rejected because accepting it (and also others generated in the same way) will ultimately lead to sampling from $q(x)$, not the desired $\tilde{p}(x)$. That's what the red line represents.
Therefore, this plot contains pretty much all there is to rejection sampling. It shows the two distributions, the two sampling stages, and the accept/reject criterion.