Random choices can simplify algorithms, but a probability guarantee must say which inputs are covered and which answers may be wrong. Complexity classes use worst-case guarantees over inputs and probability over the algorithm's own random bits, not an assumed distribution of inputs.
This unit has three aims. The first is to fix exactly what experiment a probability statement describes. The second is to define the classes and and show that their constants are conventions, because independent repetition drives the error down. The third is to separate what can be proved from first principles from what is imported. Two different amplification arguments are proved below, one resting on a cited concentration inequality and one fully elementary. Several counterexamples show where each hypothesis is needed.
Motivation and the probability space
A deterministic algorithm has one computation path on each input, and its correctness is a yes-or-no property of that path. A randomized algorithm has many paths on each input, one for every sequence of random bits it might read. Correctness then becomes a question about how large the set of good paths is. Before any theorem can be stated we must say precisely what the sample space is.
Let be a randomized algorithm whose running time on inputs of length is at most a polynomial for every choice of random bits. Such an algorithm cannot read more than random bits. We may therefore pad and regard the random input as a string chosen uniformly, and write for the output on input with random string . For a fixed input the acceptance probability is
This is a counting statement about a finite set, so no measure theory is needed. Three consequences matter throughout.
- Every acceptance probability is a rational number whose denominator is a power of two.
- The probability is attached to a fixed input . There is no hidden distribution on inputs, so a guarantee in these classes is a statement about each input separately.
- Independent repetitions correspond to concatenating strings , each drawn uniformly and independently, so the joint sample space is with the uniform measure. Independence is the product structure of this space and is not an extra assumption layered on top.
Three quantifiers therefore appear in every guarantee. The universal quantifier ranges over inputs. The probability ranges over the algorithm's own bits. The running-time bound ranges over all bit strings, including unlucky ones. Dropping the last of these changes the model, because an algorithm that runs forever on a tiny fraction of random strings is not a polynomial-time algorithm in the sense used here.
Error guarantees
Definition 1.1.1
(RP and BPP)
A language is in if a randomized polynomial-time algorithm rejects every input outside with probability , and accepts every input in with probability at least . It is in if a randomized polynomial-time algorithm returns the correct answer with probability at least on every input. The probabilities are over independent unbiased random bits; the time bound holds for every choice of those bits.
The constants are conventions: any fixed success probability strictly greater than for two-sided error can be amplified. For RP, repeating independently and accepting if any run accepts preserves zero false positives while reducing false negatives. Thus : a deterministic procedure simply ignores its random bits, and an RP algorithm can first be repeated a fixed number of times to attain the BPP success threshold.
It helps to name the two kinds of mistake. A false positive is an acceptance of an input outside , and a false negative is a rejection of an input in . An RP algorithm may make only false negatives, and only with probability at most on each member of . Its answer "accept" is therefore always trustworthy, while "reject" is only suggestive. A BPP algorithm may make either kind of mistake, but on every input, member or not, the probability of a wrong answer is at most .
Proposition 1.1.2
(Majority amplification)
Suppose each independent run of an algorithm is correct on a fixed input with probability at least . The majority of independent runs, for odd , has error probability at most . For polynomially many repetitions, the running time remains polynomial.
Proof
(Proof using Hoeffding's inequality)
Let indicate an incorrect answer on run . The independent variables lie in and . Majority is wrong only if , at least above the expectation. Hoeffding's inequality gives probability at most . The concentration inequality is used here without proof. Multiplying a polynomial running time by a polynomial number of repetitions remains polynomial.
Each hypothesis in this argument has a job. The fixed input matters because the bound is a per-input statement. Independence of the runs is what permits Hoeffding's inequality. Oddness of rules out ties, so that "majority" is well defined. The error variables need not have the same distribution, since only is used. If some runs err with smaller probability, the expected sum is smaller and the gap is at least , so the bound only improves. Hoeffding's inequality in the form used says that for independent with and any , .
How the bound depends on the advantage
The constant is not special. Writing the per-run success probability as , the quantity is called the advantage over random guessing. The same proof gives the following more general statement, which explains why any fixed success probability above may replace in the definition of .
Proposition 1.1.3
(Amplification as a function of the advantage)
Let . Suppose each of independent runs, with odd, is correct on a fixed input with probability at least . Then the majority answer is wrong with probability at most . In particular, to achieve error at most it suffices to take any odd .
Proof
(Hoeffding applied to the advantage)
Let indicate an error on run , so and satisfies . The majority is wrong only if , which is at least above the mean. Hoeffding's inequality, used without proof, gives probability at most . Setting and solving for gives . Taking recovers the bound of the previous proposition.
Counterexample mode
No advantage, no amplification
Claim: majority voting drives the error down for every per-run success probability. Let the algorithm ignore its input and output its first random bit. On every input it is then correct with probability exactly . For independent runs, the majority is correct when at least two of the three bits are correct, which has probability . By the symmetry of fair bits, the majority of any odd number of runs is also correct with probability exactly , so the error never decreases. This does not contradict the advantage bound: here , and says nothing. Repair: require a fixed advantage ; then repetitions suffice.
The dependence on is quadratic in the denominator. If is a fixed constant, or even the reciprocal of a polynomial in the input length, then polynomially many repetitions suffice for error for any polynomial , since is polynomial. If is exponentially small, the required number of repetitions is exponential and the argument gives nothing useful.
Reading the bound numerically
A bound such as is only useful once it is converted into a concrete number of repetitions. The next two examples show how to do this and how conservative the bound is.
Worked example 1.1.4
(Choosing the number of repetitions for a target error)
Let a BPP algorithm be correct with probability at least on every input. We want a majority-vote algorithm whose error is at most on every input.
By the majority amplification proposition it suffices to have with odd. Taking logarithms, , that is . Since , we get . The integers and larger satisfy the inequality, but is even and could produce a tie, so the smallest admissible odd value is . As a check, while , so as required. By contrast fails the inequality.
The proposition gives an upper bound that may be far from the truth. The next example computes the exact error of small majorities and compares it with the guaranteed bound.
Worked example 1.1.5
(Exact error of small majorities versus the guaranteed bound)
Suppose a single run errs with probability exactly on a fixed input. This is compatible with the bounded-fair-bit model: two fresh fair bits have four equally likely outcomes, and the error event can be the outcome . An exact probability would be impossible with a fixed finite fair-bit budget; in the BPP definition is an upper bound, not a required attained probability. For odd , independent repetition gives the exact majority-error probability
- For the error is .
- For the numerator is , giving , below the general bound .
- For the numerator is , giving , below .
- For the numerator is , giving , below .
The exact errors decrease across these four choices. The quoted bound remains valid because , though it is deliberately loose. Its value is a simple exponential guarantee for every odd repetition count and every collection of independent per-run error probabilities at most . Exact binomial calculations require identical probabilities; the general bound does not.
A one-sided example
Worked example 1.1.6
(A one-sided bound)
Suppose an RP algorithm accepts a yes-input with probability at least per run. On independent runs, accepting if any run accepts misses that input with probability at most . On a no-input every run rejects with probability , so the combined algorithm never accepts a no-input. Independence is needed for the product bound; repeating the same random seed need not improve the error.
Common mistake
(Probability is not over the input)
A claim that an algorithm is correct on 99% of inputs under some distribution is an average-case claim. BPP instead requires its success bound separately for every input, with probability taken over fresh internal random bits. An algorithm can perform well on average while failing consistently on a particular input.
The worked computation above uses nothing special about the constant or about a particular algorithm, so it can be stated and proved in general.
Proposition 1.1.7
(One-sided amplification)
Let be a randomized algorithm running in time such that every input outside is rejected with probability and every input in is accepted with probability at least for some . Let run on independent random strings and accept exactly when at least one run accepts. Then rejects every input outside with probability and accepts every input in with probability at least . Its running time is plus the cost of bookkeeping.
Proof
(Independence turns failure into a product)
Fix an input and let be the independent random strings. If , each run rejects for every string, or at least with probability , so all runs reject with probability , and the combined algorithm rejects. If , the combined algorithm rejects exactly when all runs reject. By independence, the probability of this event is the product of the individual rejection probabilities, each at most , hence at most . The running time is the sum of the run times plus a constant per run to record whether an acceptance occurred.
With and for a polynomial , the false-negative probability is at most . Moreover need not be : any one-sided error bound that is at most can be reduced to an exponentially small error by polynomially many repetitions, because for ; a practice item below treats the constant bound .
Inclusions among P, RP and BPP
The inclusions stated in the discussion of error guarantees are now proved, together with one further relation to . Recall that when there are a polynomial-time deterministic verifier and a polynomial such that if and only if some certificate with makes accept.
Proposition 1.1.8
(Basic inclusions)
and .
Proof
(Three inclusions)
: a deterministic polynomial-time decider for , run while ignoring its random bits, accepts every member with probability and rejects every non-member with probability .
: let witness and consider the algorithm that runs twice on independent strings and accepts if either run accepts. By the one-sided amplification proposition with and , it rejects every non-member with probability , and it accepts every member with probability at least . So it answers correctly with probability at least on every input, and it runs in polynomial time.
: let use at most random bits. Define a verifier that simulates on , using the certificate as the random string, and accepts exactly when accepts. This is a polynomial-time deterministic computation. If , the acceptance probability is positive, so at least one of the finitely many random strings makes accept, and a good certificate exists. If , no string makes accept, so no certificate is accepted.
Proof X-ray
What each inclusion uses
Each inclusion uses a different part of the definition. needs only that a deterministic algorithm may ignore its random bits. needs amplification: one run's false-negative probability is too large for the BPP threshold, so two independent runs are combined by OR, giving while non-members are still rejected with probability . is where one-sided error is essential: it is precisely the zero false-positive property that turns a good random string into a verifiable certificate. The practice items ask what breaks for BPP.
None of these arguments shows that any inclusion is strict. The question of whether the classes coincide is not settled by anything in this unit.
Practice and solutions
Quick check
(How many independent RP repetitions suffice to make the false-negative probability at most ?)
Use the one-sided bound.
Solution · Answer
Five repetitions suffice, since .
Quick check
(Why does majority voting fail to guarantee error reduction if all repetitions use exactly the same random bits?)
Think about identical outputs.
Solution · Answer
The outputs can then be identical in every repetition. Majority returns the same answer as the first run, so its error probability may be unchanged; the independent-trials bound does not apply.
Quick check
(A randomized algorithm errs with probability exactly on a fixed input. Compute the exact error probability of the majority of independent runs.)
Count the wrong runs.
Solution · Answer
The majority of three is wrong when at least two runs are wrong. The probability of exactly two errors is and of three errors is . The total is , which is smaller than the single-run error .
Quick check
(Using the exponential bound for success probability , find an odd number of repetitions that guarantees error at most .)
Solve the exponential bound.
Solution · Answer
We need , so . The smallest odd integer at least is . As a check, , so .
Quick check
(An algorithm never accepts a non-member and accepts each member with probability at least . How many independent repetitions, accepting if any run accepts, guarantee false-negative probability at most ?)
Use .
Solution · Answer
Apply one-sided amplification with : we need . Since and , the smallest sufficient number is . Equivalently, .
Quick check
(A run is correct with probability at least on a fixed input. Using the advantage proposition, find an odd number of runs for which the majority is correct with probability at least .)
Find the advantage first.
Solution · Answer
Here , so the majority is wrong with probability at most . We need , that is . The smallest odd integer at least is , and indeed . This is a sufficient count obtained from an upper bound, not necessarily the smallest number that achieves the target.
Quick check
(The proof that treats random strings as certificates. Explain why the same idea does not show .)
Which side may be wrong?
Solution · Answer
For a BPP language, a member has at least a fraction of accepting random strings, so an accepting string exists. But a non-member may still have up to a fraction of accepting strings, since BPP allows false positives. A verifier that accepts whenever the simulation accepts on the certificate would then accept some non-members, which violates the NP requirement that no certificate be accepted for a non-member. The zero false-positive property of RP is exactly what makes the simulation a sound verifier.
The continuation “Variance bounds and randomized identity tests” develops the variance argument and the polynomial identity test.