Question

Define a ZPP-machine to be a probabilistic Turning machine that is permitted three types of output on each of its branches: accept, reject, and? A ZPP. If M outputs the correct answer on every input string w with probability at least $\frac{\mathbf{2}}{\mathbf{3}}$machine M decides a language A (Accept it $\mathbf{w}\mathbf{\in }\mathbf{A}$ and reject if $\mathbf{w}\notin \mathbf{A}$ ),and M never outputs the wrong answer. On every input, M may output? with probability at most.$\frac{\mathbf{1}}{\mathbf{3}}$ Furthermore, the average running time over all branches of M on w must be bounded by a polynomial in the length of w. Show that ,$\mathbf{RP}\mathbf{\cap }\mathbf{coRP}\mathbf{=}\mathbf{ZPP}$ where ZPP is the collection of languages that are recognized by ZPP - machines.

Short answer

Solving the answer using Probabilistic Polynomial time and probability.

Step-by-step solution

Understanding the Problem 

Consider $L\in RP\cap coRP=ZPP$

Then assume$A$be an$RP$algorithm for$L$and assume$B$be an algorithm for$L$.

Consider$W$be the input. One step of our$ZPP$algorithm will be the following:

1. Run$A$on.$W$

2. Then run$B$on.$W$

3. If$A$accepts, accept.

4. If$B$reject, reject.

Note that this step takes polynomial time since each$A$and$B$take polynomial time.

5. If$A$rejects and$B$accepts, repeat.

First, show correctness.

Note that if$w\notin L$then$A$always rejects, so if$A$accepts .$w\in L$

Note that since each step has polynomial running time, it suffices to show the number of steps is polynomial in expectation (in fact, we will show it is constant in expectation).

Note that if,$w\in L$then$A$will accept with the probability at least$\frac{1}{2}$(by definition of RP). Similarly, for $w\notin L$and$B$reject. Thus, every step succeeds with the probability of at least .$\frac{1}{2}$

Assume $X$ is a random variable denoting how many steps to take. Then let $p_k=\mathrm{Pr}[X=k]$denote the probability by taking exactly k steps . $k-1$Note that$p_k$ is the probability that we fail on the first $k-1$ steps and then succeed, so

$E\left|X\right|=\sum _{k-1}^{\infty }\frac{k}{2^{k-1}}=4$

And this is ${\text{done}}^2$.

Proceeding with the solution using Probability concepts

$\mathbf{ZPP}\subseteq \mathbf{RP}$(It can be proved that $\mathbf{ZPP}\subseteq \mathbf{coRP}$ analogously) consider L be in ZPP , and A be a ZPP algorithm for L, and consider $\mathbf{p}\mathbf{\left(}\mathbf{n}\mathbf{\right)}$ be the expected running time of A on input of length n. Then build the following RP algorithm:

On input$W$of length,$n$

1. Run$A$ on$W$for time.$6p\left(n\right)$

2. If$A$accepts or rejects, output the answer .$A$

3. Otherwise (If$A$does not terminate, or outputs), reject.

Note that since$A$has expected polynomial running time$p\left(n\right)$is a polynomial, so$6p\left(n\right)$is also polynomial. It suffices to prove correctness. First, if ,$w\notin L$ then$A$will either reject, print or not terminate. In all of these cases, reject, so it is correct.

On the other hand, assume .$w\in L$ Again, three things can happen:$A$accepts,$A$prints, or$A$does not terminate in time. We are correct in the first two cases, so it suffices to show the probability of the latter two are at most$\frac{1}{2}$. The maximum likelihood of outputs$A$is at most.$\frac{1}{3}$

The probability that$A$ does not terminate in$6p\left(n\right)$ time is at most ($\frac{1}{3}$by Markov's inequality). Thus, if $w\in L$, the probability that $A$ is wrong is at most ,$\frac{1}{2}$ thus this algorithm is an $RP$ algorithm for .$L$