A randomized decision procedure is wrong either way with probability at most 1/3 per run; why does majority voting over independent repeats make it negligible?
answer
- error you can pay to shrink
- wrong in both directions, not one
- the gap away from one half
- majority over independent repeats
- exponential decay from a Chernoff bound
basics
~20 sMajority voting over k independent runs drives a two-sided error of 1/3 down exponentially in k: the wrong verdict needs more than half the runs to fail at once, which a Chernoff bound makes vanishingly unlikely. Cost grows linearly, failure falls exponentially.
solid answer
~40 sA two-sided bounded-error procedure is allowed to be wrong in both directions, but only with probability at most 1/3 on *every* input, measured over its own coin flips. Run it `k` times with fresh independent coins and take the majority: the majority is wrong only if at least half the runs are wrong, i.e. only if the observed error rate overshoots the true rate by the gap `1/2 - 1/3 = 1/6`. A concentration bound puts that at roughly `exp(-2k(1/2-p)^2)`, so error falls exponentially while cost grows linearly. The lever is the **gap away from one half**, not the number 1/3 — any constant below 1/2 defines the same class, and even a gap of `1/n` amplifies in polynomially many repeats. A procedure wrong exactly half the time amplifies to nothing.
code
pseudocode · 10 linesfunction amplify(procedure, input, k):
yes_count = 0
for i from 1 to k:
coins = fresh_independent_random_bits() // not a reused seed
if procedure(input, coins) == YES:
yes_count = yes_count + 1
if yes_count * 2 > k:
return YES
else:
return NOgo deeper
Recall that some algorithms flip coins and can be wrong, and that running them several times and taking the answer that wins the vote is what makes that acceptable.
Explain the mechanics: error at most 1/3 on every input over the algorithm's coins, majority over independent repeats, failure falling exponentially while cost grows linearly, and why the gap away from one half is the thing being spent.
Show where it breaks in a running system: repeats that share a seed, a fleet started from one source of randomness, and an error rate nobody actually measured, so no repeat count can be justified.
Frame it as a budget. Decide the failure probability the system may carry, derive the repeat count from it, and weigh that cost against the exact computation rather than adopting randomization because it sounds cheaper.
## What the guarantee actually claims A randomized decision procedure has, besides its input, a private supply of fair coin flips. It is a **two-sided bounded-error** procedure for a decision problem when, for **every** input, it returns the correct yes/no answer with probability at least 2/3 — the probability being taken over its own coins alone, never over a distribution of inputs. `BPP` is the class of decision problems that have such a procedure running in polynomial time. "Two-sided" means both mistakes are on the table: it may answer yes on a no-instance and no on a yes-instance. That distinguishes it from a one-sided procedure, where one of the two verdicts is a proof and simply cannot be wrong. Two consequences follow immediately and both routinely surprise people: - The bound is **per input**. An adversary who hand-picks the worst input still faces the same 2/3. To beat the guarantee an adversary needs influence over the *coins*, not over the data. - The bound describes **one run**. It does not say a particular answer in hand is right; it says the procedure is right that often on that input. ## Why the majority vote works Run the procedure `k` times on the same input, with fresh independent coins each time, and return whichever verdict appeared more often. Each run errs independently with probability `p <= 1/3`. The majority is wrong only when at least `k/2` runs are wrong — that is, only when the observed error rate overshoots the true rate by at least the **gap** `1/2 - p = 1/6`. A Chernoff/Hoeffding concentration bound says a deviation that large has probability at most `exp(-2k(1/2 - p)^2)`. That is the entire argument, and its shape is what to carry away: **cost grows linearly in k, failure probability falls exponentially in k.** | repeats k | bound `exp(-2k(1/2-p)^2)` at p = 1/3 | how to read it | |---|---|---| | 10 | about 0.57 | the bound says nothing useful yet | | 100 | about 4 x 10^-3 | usable for a cheap per-run cost | | 1000 | about 7 x 10^-25 | below the rate at which hardware silently corrupts a result | The bound is loose — the true majority error is smaller — but the exponent is the point, not the constant. ## The gap is the resource, not the number 1/3 Nothing is special about 1/3. Any constant strictly below 1/2 defines exactly the same class, because a fixed number of repeats converts one constant into another. Even a gap that shrinks with the input size is enough: with a gap of `1/n`, about `n^2` repeats restore a constant gap, which is still polynomial, so the class is unchanged. What destroys amplification is a gap of **zero**. A procedure that is wrong exactly half the time carries no signal at all, and a majority over its outputs is just another coin flip. Worse still is a procedure whose error you cannot bound: with no `p`, there is no `k` to choose. ## Independence is load-bearing, not a formality The concentration bound is a statement about independent trials. If every repeat draws from the same fixed seed, the `k` runs are one run performed `k` times: identical inputs, identical coins, identical (possibly wrong) verdict, and the majority inherits the single-run error unchanged. The same trap appears in weaker forms — repeats that share a derived seed, or many machines in a fleet started from one seed, fail together rather than independently. Amplification is a promise about *independent* randomness, and independence is the part an implementation can quietly lose. ## Zero error, one-sided error, and this It helps to hold three shapes apart, because engineers blur them: 1. **Always correct, random running time.** The answer is never wrong; only how long it takes varies. 2. **One-sided error.** One verdict is a proof, the other is probabilistic. Repeats multiply the error directly, since a single proof settles the matter. 3. **Two-sided bounded error**, the case here. Neither verdict is a proof, so the majority over independent repeats is the instrument, and concentration is why it works. ## What this leaves you to decide - Pick `k` from an explicit error budget, then compare the cost of `k` runs against the exact alternative. The exponential is generous: doubling `k` squares the bound. - Recognise that this guarantee is about the answer being **wrong**, not about it being **slow**; a procedure that always answers correctly but takes a random amount of time is a different contract. - Keep this separate from an approximation ratio. "Within 10% of the true value" and "wrong with probability at most 2^-40" are different promises, and a sampling estimator usually carries both at once.
- What if the per-run gap is not a constant but shrinks like 1/n?It still amplifies. Reducing a gap of 1/n to a constant takes about n^2 repeats, which is polynomial, so the resulting class is the same. Only a gap of exactly zero, or an error you cannot bound at all, defeats the argument, because then no number of repeats produces a signal to take the majority of.
- Why does a one-sided procedure need fewer repeats than a two-sided one?Because one verdict is a proof. If a single run can only err in one direction, you accept as soon as any run produces the certain verdict, and the failure probability is simply the per-run error raised to the number of repeats. A two-sided procedure has no such proof, so it needs a majority and a concentration bound instead.
- Does the guarantee survive an adversary who chooses the input?Yes. The bound is stated for every input, with the probability over the algorithm's own coins, so there is no bad input distribution to find. The realistic attack is on the randomness itself: predictable or shared coins, which break the independence that amplification depends on.
A panel of jurors who each vote correctly two times in three beats any single juror only when they deliberate separately. If all of them copy one juror's notes, the panel is exactly as reliable as that one juror, however many seats you add.
saying these in an interview costs you the question
- Treats 1/3 as a magic threshold rather than any constant below one half
- Repeats the run on the same seed and expects the error to fall
- Claims repetition rescues a procedure that is wrong exactly half the time
- Reads the bound as an average over inputs instead of per input
- Says the error becomes zero rather than exponentially small
- Confuses bounded error with a bounded approximation ratio