Why prove a special case?
The existing randomized-complexity note uses Hoeffding's inequality without proving it there. Here we prove the Bernoulli-indicator case needed for its majority argument, using a log-moment estimate and Markov's inequality. This does not prove the general theorem for arbitrary variables in .
Fix an input. Let be independent Bernoulli random variables with and . The may differ and may equal zero or one. Set and . In the application, is the indicator that the -th independent run of a randomized algorithm errs, so counts the erroneous runs. We will show, for every , that .
Bounding one centered moment
The proof rests on one function attached to a single Bernoulli variable.
Definition 6.1.1
(Centered log-moment of a Bernoulli variable)
Let be Bernoulli with . Its moment generating function is
which is positive for every real . The centered log-moment is
The identity on the right holds because is a constant that can be taken outside the expectation. The next statement says that grows at most quadratically, uniformly in .
Lemma 6.1.2
(Bernoulli moment bound)
For every and every ,
Proof
(Two integrations of a bounded second derivative)
Put . Differentiating gives , and differentiating again, using , gives
Also and . Since , we have , so everywhere. Integrating from to gives , and integrating once more gives .
No division by or occurs, so the argument covers and as well.
From moments to a tail
Theorem 6.1.3
(Exponential tail for independent Bernoulli sums)
Let be independent Bernoulli variables with , and put , . For every ,
Proof
(Markov, factorize, optimize)
For any , Markov's inequality applied to the nonnegative random variable gives
Independence factors the expectation into the product of the centered moments, and the moment bound applies to each factor:
Hence for every . The exponent is a convex quadratic in with minimum at , which is positive because and . Substituting gives .
Proof X-ray
Where each hypothesis does its work
The proof has three moves, and each uses exactly one hypothesis. Markov's inequality needs a nonnegative variable, which is why we exponentiate rather than work with itself, and is what turns the event into the event . The product step is the only place independence is used. The moment bound is then applied factor by factor, so the need not be equal, and a variable with contributes the factor . The final choice trades the linear gain against the quadratic cost ; it is the single free parameter, and it is allowed because the lemma holds for all . Without independence, individual moment bounds say nothing about the expectation of the product.
The product step is not a technicality. The next example drops independence and shows that the stated bound then fails.
Counterexample mode
Perfectly correlated runs defeat the bound
Claim: the bound holds for any Bernoulli variables, independent or not. Take and , where is one fair bit. Then each is Bernoulli with , so , but with probability each. For , the event is exactly , so its probability is . The claimed bound is . The claim is false. Independence is what makes a product; here is larger than the product of the marginal moments.
Majority amplification and an exact check
Corollary 6.1.4
(Majority vote with independent runs)
Let be odd. Suppose the runs on a fixed input are independent and each errs with probability at most . Then the probability that the majority answer is wrong is at most .
Proof
(Shifting the threshold by )
Let indicate that run errs, so . A wrong majority requires , hence . Applying the tail bound with gives , so the probability of a wrong majority is at most .
This is an upper bound, not generally the exact error. The worked examples below separate the two roles of the inequality: first checking it on a case small enough to compute exactly, then using it to choose a number of repetitions.
Worked example 6.1.5
(Exact check with three fair bits)
Let be independent fair bits, so , , and take . The event is exactly , which has probability . The bound gives . Indeed . The bound is valid but not tight. This example checks the tail theorem itself; it is not a majority example with error at most .
Worked example 6.1.6
(How many runs for error at most ?)
By the majority corollary, odd independent runs with error at most give wrong-majority probability at most . We want , that is , so . The smallest odd integer satisfying this is . As a check, gives , so the guarantee does not apply, and gives . Also, with runs the bound is . The bound is a sufficient count, not necessarily the smallest one that works.
Worked example 6.1.7
(Degenerate and unequal probabilities)
Let , and a fair bit, all independent, so , and . Then . Take . The event is , with probability , and the bound is , which is valid. The centered moments are , and , so the two deterministic variables contribute nothing. The theorem still divides by the full , so it is far from sharp here. Nothing in the proof requires .
Common mistake
(Reading the exponential as the error probability)
The quantity is an upper bound obtained from the weak assumption that each run errs with probability at most . It is not the probability of a wrong majority. In the three-fair-bit check, the exact probability is while the bound is . Report such a quantity as a guarantee, and never as an estimate of the actual error.
Common mistake
(Using a one-sided bound for a two-sided event)
The theorem bounds only. For the event one applies the theorem also to , which are independent Bernoulli variables with in the role of , and takes a union bound, so the bound becomes . Likewise is an absolute deviation: a deviation of is and gives .
Exercises with solutions
Quick check
(If , what is ?)
Compute first.
Solution · Answer
With , , so , and . Hence for all , which satisfies trivially. This is why the degenerate case needs no separate treatment.
Quick check
(Why is the choice allowed in the proof?)
Check the sign requirement on .
Solution · Answer
The hypotheses and make positive, which is the condition used in Markov's step and in the moment bound. It is also the minimizer of the quadratic exponent , since the derivative vanishes there.
Quick check
(Where does independence enter the proof?)
Look for the step that turns one expectation into several.
Solution · Answer
It enters only at the factorization of into the product of the expectations . Markov's inequality, the single-variable moment bound and the optimization of do not use it.
Quick check
(In the three-fair-bit check, is the bound equal to the exact probability?)
Compare with .
Solution · Answer
No. The exact probability is , while . The exponential expression is a valid upper bound, not an equality.