This continuation assumes the definitions of RP, BPP and independent amplification developed in the preceding note. We compare a variance bound with the earlier exponential estimate, then examine a polynomial test whose one-sided error can be counted exactly. Each probability is taken for a fixed input.
Amplification by Chebyshev's inequality
The Hoeffding argument rests on a concentration inequality that was cited, not proved. It is instructive to see that polynomial error reduction already follows from a completely elementary tool. The price is a weaker, polynomial instead of exponential, decay of the error.
Proposition 1.3.1
(Majority amplification by variance)
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 .
Proof
(Proof using Chebyshev's inequality)
Let indicate an error on run , let , and let . Then . Because the are independent, variances add, so . The function is increasing on , so gives , hence .
The majority is wrong only if . Then , so . Chebyshev's inequality states that for any , . With we obtain
Proof X-ray
What the variance bound really needs
The one non-obvious move is to turn the event "the majority is wrong" into a deviation of from its mean. The mean is only known to satisfy , so the gap is at least in the worst case, and a smaller mean only widens it; this is why the single bound is enough. The monotonicity of on is used once, to replace each unknown by its worst case. The bound closes because the variance grows like while the squared threshold grows like . If the runs shared randomness, variances would no longer add: for one has , and Chebyshev's inequality gives nothing.
Two features of this proof deserve comment. First, it uses independence only through the additivity of variance, which already holds when the runs are merely pairwise independent. The Hoeffding argument in the preceding note is not covered by this remark, since it uses full independence. Second, the conclusion is useful for reducing error to the reciprocal of a polynomial. To make the error at most it suffices to take the smallest odd , which is polynomial. This estimate alone does not give exponentially small error; the earlier exponential estimate does.
Worked example 1.3.2
(Comparing the two amplification bounds)
Let a BPP algorithm be correct with probability at least on every input, and suppose the target error is .
Using the variance bound, we need , that is . Since is even, take the smallest odd value , for which .
Using the exponential bound from the Hoeffding argument, we need , that is , so the odd value suffices. The exponential bound is therefore about ten times more efficient at this target, and the gap grows as the target error shrinks. For target error , the variance bound would require repetitions (odd value ), while the exponential bound requires only .
Both numbers are sufficient counts obtained from upper bounds, not necessarily the smallest values that achieve the target error. The comparison shows that qualitative closure of BPP under polynomial error reduction is elementary, while this direct variance estimate does not provide exponentially small error; the exponential estimate does.
Randomized identity testing
A classical use of one-sided error is checking whether two polynomials are the same function. Here the input is two polynomials and with integer coefficients, given as explicit coefficient lists, each of degree at most . We want to decide whether as polynomials, equivalently whether the difference is not identically zero.
Choose and . The algorithm picks uniformly from using fair bits. It computes and by Horner's rule and answers "different" if , and "same" otherwise. The integer has bits and Horner evaluation creates only polynomially many bits in the explicit input length, so each run takes polynomial time. Comparing the coefficient lists is already a deterministic polynomial-time solution here; this example illustrates the probability argument rather than a speedup.
The correctness argument uses a standard algebraic fact, proved below: a nonzero polynomial of degree at most with integer, or real, coefficients has at most roots. If then vanishes identically and the algorithm never answers "different", so there are no false positives for the language of unequal pairs. If then is nonzero of degree at most , so at most of the choices of satisfy , and the algorithm answers "different" with probability at least . This is exactly the RP guarantee.
Worked example 1.3.3
(A tight instance and a failing sample set)
Take and , so , and choose , which has size . The difference is , and
The algorithm detects the difference exactly when , so it answers "different" with probability and errs with probability exactly . The guarantee is therefore tight for this instance. With independent samples, accepting "different" if any sample detects, the false-negative probability is by one-sided amplification.
If instead the pair is and , the two polynomials are equal. At , for example, and . Every sample gives equality, and the algorithm correctly never answers "different".
The requirement cannot be dropped. For the same and with the smaller set , both elements are roots of , so the algorithm answers "same" with probability on this unequal pair. Repetition does not help, because every sample falls on a root. The bound on the number of roots is a statement about the density of bad choices, and the sample set must be large enough that this density is at most .
Why a polynomial has only finitely many roots
The identity test rests on a deterministic algebraic statement. Its hypotheses distinguish a nonzero polynomial from a polynomial function that happens to vanish at several sample points. The root count is a property of the polynomial over a field; it does not require choosing the sample set randomly.
Proposition 1.3.4
(Root bound over a field)
Let be a field and let be nonzero of degree . Then has at most distinct roots in .
Proof
(Proof by division and induction)
A nonzero constant has no roots. Suppose the result holds below degree and that is a root of a degree- polynomial . Polynomial division gives because the remainder is , and has degree . If is any other root, then . A field has no zero divisors and , so . By induction there are at most such further roots. Together with there are at most . If there is no first root, the bound is immediate.
The proof counts distinct roots, not multiplicities. For instance, has degree three but only one distinct root. It also relies on the coefficient domain being a field: in a ring with zero divisors the step from a zero product to a zero factor can fail. When the sample set contains more points than the degree, at least one point detects a nonzero difference, but a deterministic choice of one particular point need not detect it. Random sampling converts the count of potentially bad points into a per-input probability bound.
Concept lensGeometric
Where two graphs can meet
A sample fails to detect a difference exactly when , that is, when the graphs of and cross above . The root bound says two distinct polynomials of degree at most have graphs that meet in at most points. The test therefore errs only if the random sample lands on one of these few crossing abscissas.
Worked example 1.3.5
(A degree-three difference on eight sample points)
Let and . Its only roots are , so one uniform sample misses the difference with probability . Three independent samples all miss with probability . The exact calculation agrees with the general bound for one sample. It is the independence of the three sample choices that permits multiplication of the miss probabilities.
The result is useful even when the polynomials are equal: equality produces zero difference at every point, so this test never incorrectly reports inequality. The complementary error is possible for unequal polynomials because a sampled point can be a root. These two cases must be kept separate when assigning the one-sided error guarantee.
Counterexample mode
More than d sample points is not enough
A tempting claim is that any sample set with gives one-sided error at most , since a nonzero difference of degree at most has at most roots and so cannot vanish on all of . Take , , and , so . The difference has and , so the test detects the difference only when . The detection probability is and the error probability is , which equals the general bound . The root bound limits the error only by , so a guarantee of needs .
Limits of amplification and counterexamples
Amplification theorems have hypotheses, and each hypothesis can fail in an instructive way.
The first hypothesis is a strict advantage over guessing. Consider the algorithm that ignores its input and outputs a fair coin flip. On every input it answers correctly with probability exactly , since for a member it accepts with probability and for a non-member it rejects with probability . For odd , the number of accepting runs is distributed as a binomial with parameters and , and the symmetry shows . These two events partition the sample space, so each has probability exactly . The majority is correct with probability exactly for every odd , and no amount of repetition improves it. This is why the definition of BPP requires a probability bounded away from .
Common mistake
(An advantage must be bounded away from zero)
It is not enough for a success probability to be strictly above . If it is , the guarantee from the advantage proposition, with , falls below only once . That is exponential in , so this argument gives no polynomial-time algorithm. A BPP-style definition therefore requires a constant advantage, or at least the reciprocal of a polynomial, and the argument establishes closure under such changes of constant.
The second hypothesis is that the amplification rule matches the error type. For one-sided error, accepting if any run accepts is safe. For two-sided error it is not. Suppose an algorithm accepts a particular no-input with probability in each run, for example when two fresh fair bits are both zero. If we accept whenever any of independent runs accepts, the false-positive probability becomes . The "any run accepts" rule converts a modest false-positive probability into a large one. Two-sided error needs a majority, or a threshold calibrated to the two error rates, instead.
The third hypothesis is independence of fresh bits. If all repetitions reuse one random string, the outputs coincide and the majority equals the first run, as the exercise on reusing one sample point makes precise. Partial dependence is subtler. The variance argument needs only pairwise independence, but the exponential bound assumes the stronger mutual independence, and the product formula for the one-sided case also needs it.
Common mistake
(Averaging over inputs cannot be repaired by repetition)
Let , fix , and consider an algorithm that, on input of length , answers "no" deterministically if and answers correctly otherwise. Under the uniform distribution on inputs of length it is correct with probability . On the input it is wrong with probability , so no majority of independent runs can be correct there; the majority is wrong with probability too. The hypothesis of the majority proposition, success probability at least on the fixed input, fails at exactly the input where the algorithm is bad. High average accuracy therefore says nothing about membership in BPP.
What has been proved and what has been assumed
It is worth separating the logical status of each claim. The preceding note and this continuation prove the following from definitions and elementary probability: one-sided amplification, the inclusions and , and polynomial error reduction for two-sided error via Chebyshev's inequality, with the bound .
The variance argument uses Chebyshev's inequality without proof, and the preceding note uses Hoeffding's inequality for its exponential bounds and . The root bound proved above supports the identity test. The definition of via polynomial-time verifiers is used as the standard definition.
Finally, the unit does not determine whether , or , and nothing proved here settles those questions. The arguments show only that the stated error constants are conventions that do not change the classes.
Practice and solutions
Quick check
(Run the identity test on and with and . What is the probability that one run detects the difference, and what is the false-negative probability after three independent runs?)
Factor and count its roots inside .
Solution · Answer
The difference is . Its values on are , , , , , , and . Only and fail to detect the difference. One run detects it with probability and misses it with probability . Three independent runs all miss with probability . The actual miss probability is below the bound because the root lies outside .
Quick check
(For over the field of three elements, evaluate at every field element. How does the number of roots compare with the degree bound?)
Use the elements with arithmetic modulo .
Solution · Answer
The values are , and . There are no roots in the field, which is consistent with the upper bound of two: the root bound is an upper bound and need not be attained.
Quick check
(For the degree-three difference in the worked example, suppose the same uniformly chosen sample point is reused three times. What is the probability that all three checks miss?)
Ask how many independent random choices are actually made.
Solution · Answer
The three outcomes are identical, so they all miss exactly when the single sampled point is one of the three roots. The probability is , not ; the latter requires independent choices.