Randomness can make an algorithm fast without allowing it to give a wrong answer. Such an algorithm may occasionally take much longer than usual, so a worst-case time bound is not the right measure. A different approach insists on a fixed time limit and allows the algorithm to answer “unknown.” These two viewpoints lead to the class ZPP and explain its relationship with one-sided randomized decision procedures.
We work with languages and random bits sampled independently and uniformly. All probability and expectation statements below are for each fixed input ; no input distribution is assumed. A randomized machine's running time counts all steps, including random-bit generation. A polynomial expected-time bound means that one polynomial satisfies for every input . We may increase so that for every .
Zero error and variable running time
Definition 1.2.1
(Las Vegas decider and ZPP)
A Las Vegas decider for outputs the correct membership bit on every terminating computation path, halts with probability one on every input, and has polynomial expected running time on each input. We define as the languages with such a decider. The word “expected” is not a promise that all paths finish in polynomial time. The bound must be uniform across all inputs of each fixed length. A zero-probability infinite random sequence does not affect almost-sure termination, but every finite path on which the machine does halt must have the correct answer.
Worked example 1.2.2
(Repeated fair coins and their running time)
Consider a procedure that repeatedly flips a fair coin until the first head, then returns a predetermined correct answer. Let be the number of flips. For , the event means that the first flips were tails and has probability . The identity holds pointwise; taking expectations of its nonnegative terms yields . The procedure halts with probability one, although for every fixed there is a positive probability that it needs more than flips. The hypothetical infinite all-tails sequence has probability zero. This toy procedure illustrates the resource distinction; its answer was supplied in advance, so it is not an algorithm for an arbitrary language.
Common mistake
(Expected polynomial time is not a polynomial cutoff)
An expectation bounds an average over random choices on the same input. It permits rare long runs. Conversely, a machine that always stops quickly but sometimes gives a wrong answer is not automatically zero-error. Runtime and correctness are separate requirements; an “unknown” output is neither a yes answer nor a no answer.
Definition 1.2.3
(RP and coRP)
We also use the standard one-sided classes. A language is in RP if a polynomial-time randomized decider accepts a yes-instance with probability at least and never accepts a no-instance. It is in coRP if its complement is in RP: a coRP decider never rejects a yes-instance and rejects a no-instance with probability at least . Every random choice and probability bound is over the machine's coins for the given input. Repeating independent trials can reduce the probability of the permitted one-sided error without creating an error on the other side.
Worked example 1.2.4
(Reading the direction of a one-sided guarantee)
Suppose a randomized polynomial-time test for a language accepts a true instance with probability and accepts a false instance with probability zero. It is an RP procedure: acceptance certifies membership, while rejection may be inconclusive. Running it twice with fresh coins and accepting if either run accepts gives false-negative probability at most on a true instance, still with no false positives. If the two runs reused the same coins, their failures could be identical and the square would not be justified.
Turning expected time into an unknown answer
The key estimate is Markov's inequality. For a nonnegative random variable and , . We use it in the following form, and prove this form directly rather than importing a concentration theorem.
Proposition 1.2.5
(A cutoff for a nonnegative running time)
If a nonnegative random variable has finite expectation and , then .
Proof
(Markov's inequality by an indicator comparison)
Pointwise, . Taking expectations gives . Dividing by the positive number gives the bound. It applies whether the runtime distribution has a finite or an infinite set of possible values, provided the expectation is finite.
Worked example 1.2.6
(Cutting off a variable-time decider)
Suppose a correct randomized decider has expected runtime at most on inputs of length . Stop it after steps, rounding the cutoff upward if needed, and output “unknown” if it has not halted. Markov gives probability at most of reaching the cutoff without a result; the exact convention about a halt on the final step can only improve this bound. The new procedure always halts within a polynomial number of steps, outputs a correct answer whenever it outputs a bit, and gives that answer with probability at least . The time to check the cutoff adds only polynomial overhead.
The cutoff uses a particular polynomial bound belonging to the existence proof for the Las Vegas machine. An algorithm need not infer its own expected running time from a single execution. A different polynomial bound can be hardwired into a different construction, and finitely many small input lengths can be handled by increasing the polynomial.
Two one-sided procedures give zero error
Theorem 1.2.7
(The zero-error characterization)
.
Proof
(Two simulations in each direction)
First suppose , and take a Las Vegas decider whose expected time is at most . Run it for steps. To obtain an RP decider, accept only if the simulation has halted and returned yes by the cutoff; otherwise reject. A no-instance is never accepted because any returned answer is correct. On a yes-instance, the cutoff estimate says that the correct yes answer has appeared with probability at least , exceeding the required . The time is polynomial.
For a coRP decider, use the same bounded simulation but reject only when it has halted and returned no; otherwise accept. It never rejects a yes-instance and rejects a no-instance with probability at least . Thus lies in both classes. The two transformations map “unknown” to opposite answers because the allowed errors are on opposite sides.
Conversely, suppose has an RP decider and a coRP decider . On each round run with fresh random bits. If accepts, output yes. If it rejects, run with fresh random bits; if rejects, output no. Otherwise start a new round with independent coins. Each run of and takes polynomial time.
On a yes-instance, never rejects, while accepts in each round with probability at least . The probability of reaching round is at most , and the expected number of rounds is at most . On a no-instance, never accepts, while rejects with probability at least each round, giving the same tail and expectation bounds. The procedure can output yes only when certifies yes, and no only when certifies no, so it never outputs an incorrect answer. It terminates almost surely and has expected polynomial time, proving .
Proof X-ray
How the two one-sided classes certify each other
Each direction rests on one idea. For the non-obvious move is that one truncated simulation yields two different deciders, differing only in where "unknown" is sent: to reject for RP, to accept for coRP. This is safe because a returned bit is always correct, so the only possible mistakes are the "unknown" outcomes, and each lands on the side its class permits; the Markov cutoff bounds them by . For the converse, can only certify yes and can only certify no, and the loop outputs only upon a certificate, so no choice of coins produces a wrong bit. Termination is the only place probability enters: fresh coins in every round make the failure probability at most given the past, which gives the tail . With only , a no-instance would never produce a certificate and the loop could run forever, which is why both classes are needed.
The order of and within a round is a choice of implementation, not a change in the proof. What matters is that a yes certificate cannot occur on a no-instance, a no certificate cannot occur on a yes-instance, and each round has a fixed positive probability of yielding the appropriate certificate. The tail bound uses fresh independent randomness between rounds; without that condition, repeated failures could remain perfectly correlated.
Worked example 1.2.8
(A one-sided pair on a fixed input)
Imagine that on a particular yes-instance accepts with probability , while always accepts as soundness requires. The zero-error procedure returns yes at the first successful run of and never returns no. The probability of needing more than three rounds is , and the expected number of rounds is two. On a no-instance the roles are reversed: always rejects, and a rejecting outcome of supplies the correct no answer. The numerical values illustrate the proof for one input; class membership requires a single pair of polynomial-time algorithms with the guarantees on every input.
A bounded-time formulation
It is often convenient to package the preceding ideas as an algorithm that outputs yes, no or “unknown,” always runs in polynomial time, never outputs the wrong bit, and outputs a bit with probability at least on every input. Such an algorithm gives a ZPP decider: run independent copies until one returns a bit. If each trial takes at most steps, the probability of more than failures is at most , so the expected total time is at most plus polynomial setup. All returned bits are correct, and termination is almost sure.
Conversely, the Markov cutoff construction turns any ZPP decider into such a bounded-time three-output algorithm, with success probability at least . This is an equivalence of formulations with an explicit per-input success guarantee. A procedure that can output “unknown” forever on one input, or only succeeds on average over a selected input distribution, does not meet the stated definition.
Proposition 1.2.9
(Zero error implies bounded error)
and .
Proof
(Two independent runs)
The first inclusions follow from the characterization. For RP, run the decider twice independently and accept if at least one run accepts. On a no-instance acceptance probability is zero; on a yes-instance failure probability is at most . This meets the usual BPP threshold. For coRP, run two independent copies and reject if at least one rejects; the symmetric argument gives error at most . These inclusions do not establish that any of the classes are distinct or equal to .
Common mistake
(Correctness does not bound time)
A machine can output the correct bit whenever it halts and yet fail to be a ZPP decider: for instance, it may loop on an input with probability , or may halt almost surely but have infinite expected runtime. The definition requires both almost-sure termination and a polynomial expectation bound. Similarly, the polynomial expectation must hold for every input of a given length, not merely after averaging over inputs.
Counterexample mode
Almost-sure termination does not give polynomial expected time
A tempting claim is that a correct machine which halts with probability one on every input already has finite, hence polynomially bounded, expected running time. Let the running time be a positive integer-valued random variable with for . These probabilities sum to one because and the partial sums telescope, so is finite with probability one. Nevertheless
Hence no polynomial bound on the expectation exists. The definition of ZPP therefore asks for the expectation bound separately from almost-sure termination. The example does not claim an efficient sampling algorithm for this distribution.
Practice and solutions
Quick check
(A nonnegative runtime has expectation at most . Bound the probability that it is at least .)
Apply the cutoff proposition with .
Solution · Answer
Markov gives .
Quick check
(If an unknown-producing trial succeeds with probability at least on every independent repetition, bound the probability of three consecutive failures.)
Failures of independent trials multiply.
Solution · Answer
Independence gives probability at most .
Quick check
(Why does the RP decider made from a zero-error simulation reject on timeout?)
Which side of an RP decider may be wrong?
Solution · Answer
Timeout is inconclusive. RP permits a yes-instance to be rejected with bounded probability, but never permits a no-instance to be accepted; rejecting on timeout respects that direction.
Quick check
(Why is a fresh random tape needed in each round of the RP/coRP construction?)
Ask what the conditional failure probability of a round is given the earlier rounds.
Solution · Answer
Independent fresh tapes make the conditional probability of failure in each round at most , yielding a geometric tail. Reusing one random tape could make the same failing outcome repeat forever.
Quick check
(If a zero-error machine halts almost surely but has infinite expected time on some input, does it satisfy the ZPP definition used here?)
Compare the two requirements in the definition.
Solution · Answer
No. Almost-sure termination alone does not supply the required polynomial expected-time bound.
Quick check
(Does the equality prove ?)
Which class does the equality identify with the intersection?
Solution · Answer
No. The equality identifies the intersection with ZPP. It says nothing by itself about whether the two one-sided classes coincide.