In an accept-reject algorithm, we need to find c such that pj/qj≤ c for all j for which pi > 0 . And, the probability of accepting in any iteration is 1/c. Why is c guaranteed to be more than 1?
Asked
Active
Viewed 343 times
1
-
1@Taylor - this question appears to me to be specifically about why $c > 1$, which is not addressed in the linked question. – jbowman Aug 23 '19 at 02:46
-
@jbowman I agree with you, but in light of the information provided by the answer in that thread, the present question is equivalent to "why is the probability of an event, given by $1/c,$ guaranteed to be less than or equal to $1$?" That doesn't need a specific additional answer. – whuber Sep 09 '19 at 15:29
1 Answers
1
Consider $c < 1$. That would imply that for every value of $j$, $p_j < q_j$. But the integral of $q$ over $j$ equals 1 (it must, for $q$ to be a probability distribution); therefore the integral of $p$ over $j$ is less than 1, and $p$ is not a proper probability distribution.
Now consider $c = 1$. By a similar logic, either $p = q$ almost everywhere or $p < q$ somewhere (at least one point if discrete, over a set of measure $>0$ if continuous). In the former case, you are effectively sampling from the distribution itself, so you don't need to use acceptance-rejection sampling (and you will always accept anyway.) In the latter case, $p$ is not a proper probability distribution, by the same logic as in the $c < 1$ case.
Therefore, $c > 1$, or you are wasting your time!
jbowman
- 31,550
- 8
- 54
- 107