I am working with Markov Chain Monte Carlo (MCMC) methods and I have come across several examples of "cascaded evaluation" of log probabilities.
For example, suppose you have a rejection criterion of the form:
$$r > p_1p_2p_3$$
where $r$ is a random number drawn from the uniform distribution $U(0,1)$, and $p_1$, $p_2$, $p_3$ are independent probabilities with values between 0 and 1.
In log probability, the inequality can be written as:
$$\mathrm{log}(r) > \mathrm{log}(p_1)+\mathrm{log}(p_2)+\mathrm{log}(p_3)\tag{1}$$
In order to save compute time, I have seen that some people evaluate the inequality by doing a "cascaded evaluation":
- Draw $r_1$ as a single random number from the uniform distribution
- If $\mathrm{log}(r_1) > \mathrm{log}(p_1)$, then reject
Else Draw $r_2$ as a single random number from the uniform distribution
If $\mathrm{log}(r_2) > \mathrm{log}(p_2)$, then reject
-Else Draw $r_3$ as a single random number from the uniform distribution
-If $\mathrm{log}(r_3) > \mathrm{log}(p_3)$, then reject
This saves time because if you reject on the first if statement, you can avoid all the additional inequalities. However, I don't understand how this method satisfies the original inequality in $(1)$. Drawing multiple random numbers and evaluating each part of the summation separately doesn't seem to make sense because the full summation could still hold even if you reject all the individual parts.
Am I missing something obvious here? Or is there something special about the properties of log probabilities and/or uniform distributions and/or inequalities?
Any info is appreciated.
If the goal is to accept with probability $p_1 p_2 p_3$ then it suffices to do three independent checks that would result in acceptance with probability $p_i$, and accept only if all three checks passed (since then the probability that all three checks passed is $p_1 p_2 p_3$ as desired).
One way to describe this mathematically is to say that if $X_i$ are independent Bernoulli($p_i$) variables then $\prod_{i=1}^n X_i$ is a Bernoulli($\prod_{i=1}^n p_i$) variable. Then as soon as any $X_i$ is known to be zero, the product $\prod_{i=1}^n X_i$ can be short-circuit evaluated without needing to know the other $X_i$.