[proofplan] Here $RP$ denotes randomized polynomial time with one-sided error, $coRP$ denotes the class of languages whose complements lie in $RP$, and $ZPP$ denotes zero-error randomized expected polynomial time. We prove both inclusions. For $RP \cap coRP \subseteq ZPP$, we run the one-sided-error recognizer for $L$ and the one-sided-error recognizer for $\overline{L}$ in independent repeated rounds until one of them accepts; the accepting machine certifies the correct answer, and the expected number of rounds is bounded by a constant. For $ZPP \subseteq RP \cap coRP$, we truncate the zero-error expected-polynomial-time algorithm after twice its expected time bound and prove the needed one-sided success probability directly from the elementary Markov estimate. [/proofplan] [step:Turn one-sided recognizers for $L$ and $\overline{L}$ into a zero-error algorithm] Assume $L \in RP \cap coRP$. By $L \in RP$, there is a randomized algorithm $M_1$ and a polynomial \begin{align*} q_1: \mathbb{N} \to \mathbb{N} \end{align*} such that, for every input $x$ of length $n$, the algorithm $M_1$ halts within $q_1(n)$ steps, accepts with probability at least $1/2$ when $x \in L$, and accepts with probability $0$ when $x \notin L$. By $L \in coRP$, the complement $\overline{L}$ belongs to $RP$. Hence there is a randomized algorithm $M_0$ and a polynomial \begin{align*} q_0: \mathbb{N} \to \mathbb{N} \end{align*} such that, for every input $x$ of length $n$, the algorithm $M_0$ halts within $q_0(n)$ steps, accepts with probability at least $1/2$ when $x \notin L$, and accepts with probability $0$ when $x \in L$. Define a randomized algorithm $A$ as follows. On input $x$, repeat independent rounds. In each round, run $M_1$ on $x$ using fresh random bits and run $M_0$ on $x$ using fresh random bits. If $M_1$ accepts, output yes. If $M_1$ does not accept and $M_0$ accepts, output no. If neither accepts, start another round. If $x \in L$, then $M_0$ accepts with probability $0$, while $M_1$ accepts with probability at least $1/2$ in each round. Thus $A$ can only output yes, and in each round it halts with probability at least $1/2$. If $x \notin L$, then $M_1$ accepts with probability $0$, while $M_0$ accepts with probability at least $1/2$ in each round. Thus $A$ can only output no, and in each round it halts with probability at least $1/2$. Let $N_x: \Omega \to \mathbb{N}$ denote the number of rounds used by $A$ on input $x$, defined on the probability space $\Omega$ of all random bit sequences used by the repeated simulations. Since every round halts the algorithm with probability at least $1/2$, independently of previous failed rounds, for every integer $k \geq 0$ we have \begin{align*} \mathbb{P}(N_x > k) \leq 2^{-k}. \end{align*} For completeness, we use the elementary tail formula for a non-negative integer-valued [random variable](/page/Random%20Variable), obtained by writing $N_x = \sum_{k=0}^{\infty} \mathbb{1}_{\{N_x > k\}}$ pointwise and taking expectations. Applied to $N_x$, it gives \begin{align*} \mathbb{E}[N_x] = \sum_{k=0}^{\infty} \mathbb{P}(N_x > k) \leq \sum_{k=0}^{\infty} 2^{-k} = 2. \end{align*} Each round takes at most $q_1(n) + q_0(n)$ steps on inputs of length $n$. Therefore the expected running time of $A$ on inputs of length $n$ is at most \begin{align*} 2(q_1(n) + q_0(n)). \end{align*} Thus $A$ is zero-error, always outputs the correct answer when it halts, and has expected polynomial running time. Hence $L \in ZPP$. [guided] We want to convert two one-sided-error algorithms into one zero-error algorithm. The one-sided property is the key: an acceptance by the $RP$ algorithm for $L$ is a certificate that the input is in $L$, because that algorithm never accepts inputs outside $L$. Similarly, an acceptance by the $RP$ algorithm for $\overline{L}$ is a certificate that the input is not in $L$. Since $L \in RP$, choose a randomized algorithm $M_1$ and a polynomial \begin{align*} q_1: \mathbb{N} \to \mathbb{N} \end{align*} such that, for every input $x$ of length $n$, $M_1$ halts within $q_1(n)$ steps, accepts with probability at least $1/2$ if $x \in L$, and accepts with probability $0$ if $x \notin L$. Since $L \in coRP$, the complement $\overline{L}$ is in $RP$. Therefore choose a randomized algorithm $M_0$ and a polynomial \begin{align*} q_0: \mathbb{N} \to \mathbb{N} \end{align*} such that, for every input $x$ of length $n$, $M_0$ halts within $q_0(n)$ steps, accepts with probability at least $1/2$ if $x \notin L$, and accepts with probability $0$ if $x \in L$. Now define the zero-error algorithm $A$. On input $x$, it runs repeated independent rounds. In each round it runs $M_1$ on $x$ with fresh random bits and runs $M_0$ on $x$ with fresh random bits. If $M_1$ accepts, $A$ outputs yes. If $M_1$ does not accept and $M_0$ accepts, $A$ outputs no. If neither machine accepts, $A$ repeats the round. Why is this zero-error? If $x \in L$, then $M_0$ is being run on an input outside $\overline{L}$, so the one-sided-error guarantee for $M_0$ says that $M_0$ accepts with probability $0$. Thus $A$ cannot output no. In the same case, $M_1$ accepts with probability at least $1/2$, so each round halts with the correct answer yes with probability at least $1/2$. If $x \notin L$, the symmetric statement holds: $M_1$ accepts with probability $0$, while $M_0$ accepts with probability at least $1/2$, so $A$ cannot output yes and each round halts with the correct answer no with probability at least $1/2$. Let $N_x: \Omega \to \mathbb{N}$ be the random variable giving the number of rounds used by $A$ on input $x$, where $\Omega$ is the probability space of all random bit sequences used in the repeated simulations. Because fresh independent random bits are used in every round, the probability of failing to halt for $k$ consecutive rounds is at most $(1/2)^k$. Therefore, for every integer $k \geq 0$, \begin{align*} \mathbb{P}(N_x > k) \leq 2^{-k}. \end{align*} For a non-negative integer-valued random variable, the elementary tail formula says that the expectation is the sum of its tail probabilities. Here this follows from the pointwise identity $N_x = \sum_{k=0}^{\infty} \mathbb{1}_{\{N_x > k\}}$ and taking expectations. Applying this identity to $N_x$ gives \begin{align*} \mathbb{E}[N_x] = \sum_{k=0}^{\infty} \mathbb{P}(N_x > k). \end{align*} Using the bound on the tail probabilities gives \begin{align*} \mathbb{E}[N_x] \leq \sum_{k=0}^{\infty} 2^{-k} = 2. \end{align*} Finally, each round takes at most $q_1(n) + q_0(n)$ steps on an input of length $n$. Hence the expected running time of $A$ is at most \begin{align*} 2(q_1(n) + q_0(n)). \end{align*} This is a polynomial in $n$. The algorithm $A$ has zero error and expected polynomial running time, so $L \in ZPP$. [/guided] [/step] [step:Truncate a zero-error expected-time algorithm to obtain an $RP$ algorithm for $L$] Assume $L \in ZPP$. Then there is a randomized algorithm $A$ and a polynomial \begin{align*} p: \mathbb{N} \to [1,\infty) \end{align*} such that, for every input $x$ of length $n$, the algorithm $A$ outputs the correct answer, and its running time $T_x: \Omega \to \mathbb{N}$ satisfies \begin{align*} \mathbb{E}[T_x] \leq p(n). \end{align*} Since $p$ is an explicit polynomial time-bound for the zero-error algorithm, choose an integer-valued computable polynomial \begin{align*} r: \mathbb{N} \to \mathbb{N} \end{align*} such that $r(n) \geq 2p(n)$ for every $n \in \mathbb{N}$. Define the deterministic cutoff function $\tau: \mathbb{N} \to \mathbb{N}$ by $\tau(n) := r(n)$. We prove the needed elementary tail estimate for the non-negative random variable $T_x$ directly. Since $T_x$ is non-negative, the event $\{T_x > \tau(n)\}$ implies the lower bound $T_x > \tau(n)$ on that event, and hence \begin{align*} \mathbb{E}[T_x] \geq \tau(n)\mathbb{P}(T_x > \tau(n)). \end{align*} Because $\tau(n) \geq 2p(n)$ and $\mathbb{E}[T_x] \leq p(n)$, it follows that \begin{align*} \mathbb{P}(T_x > \tau(n)) \leq \frac{p(n)}{\tau(n)} \leq \frac{1}{2}. \end{align*} Now define a randomized algorithm $B_1$ for $L$. On input $x$ of length $n$, simulate $A(x)$ for at most $\tau(n)$ steps. If $A$ halts within that time and outputs yes, then $B_1$ accepts. In every other case, $B_1$ rejects. If $x \notin L$, then the zero-error property of $A$ implies that $A$ never outputs yes. Hence $B_1$ accepts with probability $0$. If $x \in L$, then whenever $A$ halts within $\tau(n)$ steps it outputs yes, so \begin{align*} \mathbb{P}(B_1 \text{ accepts } x) = \mathbb{P}(T_x \leq \tau(n)) \geq \frac{1}{2}. \end{align*} The running time of $B_1$ is bounded by $\tau(n)$ plus the polynomial overhead of simulation, so it is polynomially bounded. Therefore $L \in RP$. [/step] [step:Use the same truncation to obtain an $RP$ algorithm for $\overline{L}$] Define a randomized algorithm $B_0$ for $\overline{L}$ as follows. On input $x$ of length $n$, simulate $A(x)$ for at most $\tau(n)$ steps. If $A$ halts within that time and outputs no, then $B_0$ accepts. In every other case, $B_0$ rejects. If $x \in L$, then the zero-error property of $A$ implies that $A$ never outputs no. Hence $B_0$ accepts with probability $0$. If $x \notin L$, then whenever $A$ halts within $\tau(n)$ steps it outputs no, so the same elementary truncation estimate gives \begin{align*} \mathbb{P}(B_0 \text{ accepts } x) = \mathbb{P}(T_x \leq \tau(n)) \geq \frac{1}{2}. \end{align*} The running time of $B_0$ is polynomially bounded by the same cutoff $\tau(n)$ and simulation overhead. Thus $\overline{L} \in RP$, which is exactly $L \in coRP$. Together with $L \in RP$, this proves that $L$ belongs to $RP \cap coRP$. [/step] [step:Combine both inclusions] The first step proved that every language in $RP \cap coRP$ belongs to $ZPP$. The second and third steps proved that every language in $ZPP$ belongs to both $RP$ and $coRP$. Therefore \begin{align*} ZPP = RP \cap coRP. \end{align*} This completes the proof. [/step]