Why is ZPP = RP ∩ co-RP?

Question

I am trying to prove the theorem that ZPP = RP $\; \cap \; co-RP$. If $L \in \; \subseteq RP \; \cap \; co-RP$ then I can see that it belongs to $ZPP$. But I am unable to prove the reverse direction, as definitions of $RP$ and $co-RP$ don't include Turing machines whose expected running time is polynomial, but $ZPP$'s definition does. Am I missing something ? How should I proceed ?

Answer 1

The solution is given in the link provided by you in wikipedia article ZPP. See the section Intersection Definition in the link. You need to know about Markov's Inequality though.

Markov's inequality is $P[ X \geq a] \leq E[X]/a$ if $X \geq 0$. If we substitude $a = 2E[X]$ then we will have $P[ X \geq 2 E[X]] \leq 1/2$.

So, basically we run the algorithm that witnesses $L \in \textrm{ZPP}$ for at least double its expected running time. If it gives an answer, then we give that answer. If it doesn't give any answer before we stop it, we give NO answer. The probability of incorrect NO answer is $\leq 1/2$. This polynomial time algorithm proves $L \in \textrm{RP}$.

If we give answer YES on forced stoppage then that algorithm proves $L \in \textrm{co-RP}$. Thus $\textrm{ZPP} \subseteq \textrm{RP} \cap \textrm{co-RP}$.

For the sake of completeness, I also give the proof of $\textrm{RP} \cap \textrm{co-RP}\subseteq\textrm{ZPP}$.

Suppose we have a language $L \in \textrm{RP} \cap \textrm{co-RP}$. Then $L$ has a polynomial time algorithm $A$ that answers YES at least 1/2 times for $x \in L$ and a polynomial time algorithm $B$ that answers NO at least 1/2 times for $x \not\in L$. In one iteration we do the following: Given an input $x$ in $L$, we run $A$ on $x$. If it returns YES, the answer must be YES, so we return YES. Otherwise, we are in doubt so we run $B$ on the input. If it returns NO, the answer must be NO, so we return NO. If neither occurs, we repeat this iteration. We can show that the expected running time of this algorithm is still polynomial. Thus $\textrm{RP} \cap \textrm{co-RP}\subseteq\textrm{ZPP}$.