How to combine two Monte Carlo algorithms into a Las Vegas one?

Question

Consider a decision problem $D$ with corresponding Monte Carlo algorithms $X$ and $Y$ satisfying the following properties:

• If $D(s)$ is true, then $X$ returns true with probability $p$ and false otherwise. If $D(s)$ is false, then $X$ always returns false (in particular, if $X$ returns true, it is always correct).
• If $D(s)$ is true, then $Y$ always returns true. if $D(s)$ is false, then $Y$ returns false with probability $q$ and true otherwise (in particular, if $Y$ returns false, it is always correct).

Can we use $X$ and $Y$ to construct a Las Vegas algorithm solving $D$?

Answer 1

If we want to be correct, we'd better only use processes we can be confident are correct. In particular, there's really only one thing we can do.

def L(s):
  loop:
    if X(s) returns true, return true
    if Y(s) returns false, return false

Clearly this is correct provided that it terminates by the definitions of $X$ and $Y$. We now argue that this algorithm has finite expected runtime. Let $T_X(n)$ and $T_Y(n)$. The expected runtime of $L$ is simply $T_X(n)+T_Y(n)$ times the expected number of iterations of this program. To compute that, we note that the probability of the program not halting on any given iteration is at most $r=\max\{1-p,1-q\}$, as we either need $X$ to incorrectly return false or $Y$ to incorrectly return true to not halt. In particular, the number of iterations is a geometric random variable with parameter $r$ and thus expected value $\tfrac 1r$, which is finite.