The input is fixed; the algorithm's coins are random
A randomized algorithm can give different answers on the same input. Its correctness claim must say which answers can be wrong, how likely an error is, and what the probability is taken over. These details decide which repetition rule is safe. Repeating a test and accepting whenever one run accepts is excellent for some one-sided tests, but can make a two-sided test less reliable.
We study decision problems, represented by languages . An input is a yes-instance when . Throughout this note, an error probability is measured over the algorithm's fair random bits for each fixed input. No distribution on inputs is assumed.
Three different correctness contracts
Definition 7.1.1
(Polynomial-time randomized decision algorithms)
An algorithm receives an input and a random tape . There is a polynomial bound on its running time for every input of length and every random tape. It therefore uses at most a polynomial number of random bits. Pad unused bits so that tapes of a given input length all have the same length; choose them uniformly.
The following are contracts for an algorithm recognizing :
| Class | If | If |
|---|---|---|
| RP | Accepts with probability at least | Never accepts |
| coRP | Always accepts | Accepts with probability at most |
| BPP | Accepts with probability at least | Accepts with probability at most |
A language belongs to a class if some algorithm with that contract exists. Here the time bound is worst-case over the random tape, not merely an expected-time bound.
For RP, an acceptance is conclusive evidence of a yes-instance; a rejection might mean that the random trial missed a witness. For coRP, a rejection is conclusive evidence of a no-instance. For BPP, either answer can be wrong. The table does not allow an algorithm to be correct only on most inputs: every individual input must meet its row's bounds.
The constants are useful reference points. What matters for amplification is a suitable gap from the relevant failure threshold. We will prove the needed bounds for the constants in the table rather than silently assume that every repetition procedure works.
RP amplification preserves the conclusive answer
Run an RP algorithm times with independent fresh random tapes, and accept if at least one run accepts. On a no-instance, every run rejects, so false acceptance remains impossible. On a yes-instance, let be the probability that a single run rejects. All runs must reject for the repeated algorithm to fail. Independence gives
For a target error , choose . The repeated running time and random-bit use grow by a factor of .
Worked example 7.1.2
(A small sampling test with a one-sided contract)
Let the input be four bits, and ask whether at least one is 1. A trial samples three indices independently and uniformly with replacement, accepting if a sampled bit is 1. On the all-zero input it cannot accept. If at least one bit is 1, the worst case has exactly one such bit, so the rejection probability is
Thus this fixed-size example has the RP error contract. For input
0010, the acceptance probability is . Two independent
three-sample trials, combined by OR, miss the 1 with probability
.
This is a transparent illustration of the contract, not a claimed speedup: reading all four bits solves this small problem deterministically.
For coRP, use the dual rule: accept only if all runs accept. Yes-instances remain accepted with certainty, while the false-acceptance probability on a no-instance is at most .
Two repetitions already put either one-sided class inside BPP: the remaining possible error is at most . Deterministic polynomial-time algorithms fit both one-sided contracts by ignoring their random tapes. Complementing a BPP algorithm's output also preserves its error bound, so BPP is closed under complement.
Counterexample mode
OR can amplify the wrong answer
Suppose a BPP algorithm accepts a particular no-instance with probability . Accepting if any of independent runs accepts gives false-acceptance probability , which approaches 1. With three runs it is .
Likewise, requiring all runs to accept can destroy the guarantee on a yes-instance. A run with acceptance probability would then be accepted with probability , approaching 0.
The aggregation rule must match the error contract. Repetition alone does not specify a correct amplification algorithm.
Majority works for two-sided bounded error
For BPP, run independent repetitions with odd and return the majority answer. Fix an arbitrary input . Let be 1 when run is wrong and 0 otherwise. Each error probability is at most , and the are independent because the random tapes are independent. The majority is wrong only when at least runs are wrong.
Theorem 7.1.3
(An elementary exponential majority bound)
For odd , independent repetition and majority give, on every fixed input,
Since , the bound decreases exponentially with .
Proof
(Use a nonnegative exponential to detect many errors)
For any nonnegative random variable and , : on the event , its contribution to the expectation is at least times that event's probability. This is Markov's inequality.
Write . A majority error implies , so . Also, if , then . Independence gives
The equality that factors the expectation is precisely where independence is used. The proof does not need independence between the algorithm's behavior on different inputs.
Proof X-ray
Where the proof uses each hypothesis
The proof has three moving parts. The base makes easy to compute and turns into ; a different base would give a different constant. The error hypothesis enters only through , so the proof needs no exact value of . Independence is used exactly once, to factor into a product; Markov's inequality and the per-factor bound hold without it. Finally, the base of the final exponent is for error , which is below exactly when , so this elementary computation uses the gap between and that threshold.
Choose an odd integer at least
to make the bound at most . This is repetitions. In particular, error for a positive polynomial can be reached in polynomial time from a BPP algorithm. An arbitrarily tiny requested error is not free: if is exponential in input length, this amplification procedure need not remain polynomial-time.
Worked example 7.1.4
(How many runs for error at most ?)
Suppose we want error at most from a BPP algorithm. The bound requires , so the smallest odd choice is . To see how loose this is, suppose each run errs with probability and take . The exact majority error is , while the bound gives . The bound is valid but conservative: it certifies an exponential rate, not the smallest number of repetitions.
A bound need not equal the exact error
Worked example 7.1.5
(Exact majority error for three runs)
Suppose, for this calculation, that three independent runs each have error probability exactly on a fixed input. This rate is compatible with a finite uniform fair-bit tape, unlike an exact rate of ; the BPP definition uses as a bound, not an attainable equality requirement. The number of wrong runs has the following distribution:
| Wrong runs | Probability | Majority wrong? |
|---|---|---|
| 0 | No | |
| 1 | No | |
| 2 | Yes | |
| 3 | Yes |
Thus the exact majority error is , below . Our general exponential bound is deliberately loose for this small number of trials; it proves a uniform rate of decrease, not an exact binomial tail.
Counterexample mode
Copying a random tape creates no new evidence
Claim: three runs that each err with probability always give majority error . Suppose the base algorithm errs on exactly one quarter of its random tapes for a fixed input, and run it three times using the same tape each time. Because input and tape determine the computation, all three answers are identical, so the majority is wrong on exactly the tapes where one run is wrong. The error remains , not . Each run separately has the right error probability, but their correlation invalidates the product step in the proof of the majority bound. Repair: use fresh independent tapes for the runs; independence is an assumption of the amplification theorem, not a cosmetic implementation choice.
One good tape for a whole input length
The BPP guarantee first fixes and then takes probability over . It does not say that a particular sampled tape works simultaneously for every input. There may be different bad tapes for different inputs. Nevertheless, amplification plus a finite union bound gives a useful existence statement.
Theorem 7.1.6
(A polynomial-length tape can work for every length-n input)
Let . For each input length , amplify the error to at most per input. There exists a single random tape for that amplified algorithm which gives the correct answer on all binary inputs of length .
Proof
(Pay for all inputs with a union bound)
At this input length, pad the amplified algorithm's random tape to a common polynomial length . For each , let be the event that a uniformly chosen tape makes the algorithm err on . Every event has probability at most . Therefore
The union bound needs no independence between these events. With probability at least , a tape belongs to none of them, so at least one good tape exists. The required amplification uses repetitions, hence remains polynomial.
Concept lensCombinatorial
A table of inputs and random tapes
Form a table with one row for each input of length and one column for each random tape, marking the cell when the algorithm errs. Each row has at most a fraction of marked cells, so at most of the columns contain any mark. At least half the columns are therefore unmarked, and each unmarked column is a tape that is correct for every input at once.
This yields a nonuniform consequence.
Definition 7.1.7
()
A language is in if there are a polynomial , advice strings of length depending only on the input length , and a deterministic polynomial-time machine such that if and only if accepts.
Corollary 7.1.8
(BPP is contained in P/poly)
.
Proof
(Advice is the good random tape)
Let . For each length , take the good tape of the amplified algorithm from the previous theorem as the advice . A deterministic polynomial-time machine simulates the amplified algorithm on with this fixed tape. By the choice of , every length- input is answered correctly, so .
Common mistake
(Advice is not derandomization)
The quantifiers matter: for every length there exists suitable advice. The proof does not give a uniform polynomial-time procedure for finding that advice. It therefore does not prove , nor that one constant tape can simply be reused at every input length. An existence argument for advice and an executable uniform derandomization algorithm are different conclusions.
Solved exercises
Quick check
(Independent sampling versus repeated sampling results)
For the four-bit sampling test on 0010, compute the failure probability
of two independent three-sample trials combined by OR. What happens if
the second trial reuses the same three sampled indices?
Solution · Answer
One trial fails with probability . Independent trials both fail with probability . Reusing the same three indices gives exactly the same observed bits, so the combined failure probability stays . OR is the right one-sided rule, but multiplication of failure probabilities still needs independence.
Quick check
(Compute five-run majority error)
Assume five independent runs each have error probability exactly on a fixed input. Compute the exact majority-error probability. If that input is a no-instance, what false-acceptance probability would an OR rule give instead?
Solution · Answer
The majority is wrong with three, four or five erroneous runs:
On a no-instance, each error is an acceptance. OR falsely accepts unless all five runs reject, giving . Majority improves the two-sided error; this OR rule increases it.
Quick check
(Make a simultaneous claim at length ten)
Suppose one common-length random tape gives per-input error at most on every ten-bit input. Bound the probability that the tape is bad for at least one ten-bit input. Must error events for different inputs be independent? What does existence of a good tape fail to supply?
Solution · Answer
There are inputs. The union bound gives probability at most that some input is answered incorrectly, so a tape good for all ten-bit inputs exists, with probability at least . Independence across inputs is unnecessary. The existence proof does not provide a uniform efficient algorithm for finding a good tape for each length; this is the missing step in a uniform derandomization claim.
Quick check
(Small average error is a different promise)
Let be the empty language. For inputs of length , a deterministic algorithm accepts only and rejects all other strings. Its error under a uniform random length- input is . Does this algorithm meet the BPP contract for the empty language?
Solution · Answer
No. On the fixed input , which is a no-instance, it accepts with probability 1. Its small average error over a distribution of inputs cannot repair this violation of the per-input requirement. The empty language itself is of course in P and BPP: the always-reject algorithm recognizes it correctly. The failure belongs to the proposed algorithm, not to the language's class membership.