1
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ @Taylor - this question appears to me to be specifically about why $c > 1$, which is not addressed in the linked question. $\endgroup$
    – jbowman
    Aug 23, 2019 at 2:46
  • $\begingroup$ @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. $\endgroup$
    – whuber
    Sep 9, 2019 at 15:29

1 Answer 1

1
$\begingroup$

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!

$\endgroup$

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