How unlikely is a large deviation?
The weak law says that an average of independent identically distributed variables with finite variance approaches its mean in probability. For a finite sample, however, a student often needs a numerical upper bound on the chance of a specified error. Chebyshev's inequality uses only the variance and gives a bound proportional to for a fixed error. When the observations are independent and bounded, the exponential transform carries more information and yields a bound that decreases exponentially in .
Write . For any for which the expectation is finite, Markov's inequality applied to the positive random variable gives
Every permitted gives a valid bound; choosing is part of the method. Independence factors the expectation into the product of the individual exponential moments. It is this factorization, together with a bound on each factor, that produces the sample-size improvement.
The bounded exponential-moment lemma
Theorem 20.1.1
(Hoeffding's lemma)
If is a real random variable satisfying almost surely, with , then for every real ,
When , the centered variable is zero and the same bound holds with right side .
Proof
(Curvature of the log moment-generating function)
Put and . Boundedness permits differentiation under the expectation for every real . Under the tilted probability measure whose density is , differentiation gives and . The tilted law still puts in an interval of length .
For any random variable in an interval , implies , and hence
Thus . Since , integrating this bound twice from to gives . For the same conclusion follows by applying the argument to and . Exponentiation proves the lemma.
Proof X-ray
Why the square of the range appears
The proof never bounds directly. It passes to and controls its curvature. Boundedness of is used twice: it justifies differentiating under the expectation for every real , and it survives exponential tilting, since the tilted law has the same support and so keeps in an interval of length . Centering is used once, to give ; together with this removes the constant and linear terms from the Taylor bound.
The key move is recognizing as a variance under the tilted law and bounding every such variance by the same constant . That uniform bound is what the double integration turns into . A bound on the variance at alone would control and say nothing about away from zero. The square of the range thus enters as the largest possible variance of a variable confined to an interval of that length.
Theorem 20.1.2
(Hoeffding inequality for a sum)
Let be independent, with almost surely, and let . If and , then
Consequently the two-sided probability is at most . If , the sum is constant almost surely and either deviation has probability zero.
Proof
(Optimizing the quadratic exponent)
By independence and the lemma, the upper tail is at most for every . The quadratic is minimized at , giving the stated exponent. Apply the same argument to for the lower tail, and use the union bound for both tails.
If the independent variables all lie in , putting yields
They need not have the same distribution: the center here is the average of their separate expectations. For iid observations it is their common mean .
Common mistake
(One tail is not two tails)
The bound controls a single tail. An event such as is the union of two tails, so the union bound adds the two estimates and the factor cannot be dropped. In the sample-size example below, dropping it would replace by and understate the requirement as instead of .
Worked example 20.1.3
(A finite-sample accuracy guarantee)
Suppose are iid measurements in , with unknown mean . To guarantee that the displayed upper bound for is at most , it is enough that
Thus suffices. This is a sufficient worst-case sample size, not a claim that the actual error probability equals or that fewer observations cannot work for a particular distribution.
Worked example 20.1.4
(Chebyshev and Hoeffding for the same guarantee)
Keep the setting of the previous example. A variable in has variance at most , by the interval variance bound used in the proof of the lemma. Chebyshev's inequality therefore gives
which is at most only when , about nine times the Hoeffding requirement . For small samples both bounds can be uninformative. At , Chebyshev gives , and Hoeffding gives , which exceeds one and therefore says nothing. The exponential bound helps only once is large enough for the exponential to overcome the factor .
Retaining the Bernoulli distribution
A range-only bound ignores the success probability. Keeping it gives a sharper exponent.
Theorem 20.1.5
(Chernoff bound for Bernoulli sums)
Let be iid Bernoulli with , so counts successes, and put
If , then . If , then .
Proof
(Optimizing the exponential parameter)
For and , Markov's inequality and independence give
The log of the right side divided by has derivative . Its unique zero is , where . Substitution yields
For , apply the upper-tail case to the number of failures , which is binomial with success probability : the event is , with , and .
The threshold need not be an integer; the event means . The endpoint cases and follow directly: their probabilities are and , respectively. These inequalities bound tail probabilities, while is a function of two probabilities; it is not a distance because it is not generally symmetric.
Common mistake
(The Chernoff exponent applies only beyond the mean)
The upper-tail bound requires . Since for every , using it on the wrong side of the mean produces a falsely small number. For and , the choice gives and , yet is close to one: the correct lower-tail bound gives , hence .
Worked example 20.1.6
(A biased coin)
For , and , the Chernoff bound is
The range-only one-sided Hoeffding bound uses and gives . The Chernoff bound is sharper in this example. Neither bound is the exact binomial tail.
Counterexample mode
Identical observations are not independent
Let , where is Bernoulli. Every lies in , but and for every . Substitution into the independent-variable bound would eventually give a number below . Boundedness and identical distributions cannot replace independence.
Exercises
Quick check
(Independent variables satisfy almost surely. Give a two-sided bound for .)
Solution · Answer
The common range has length , so the bound is . The mean in the event is the average of the individual means; identical distribution is unnecessary.
Quick check
(Independent satisfy and . Bound .)
Solution · Answer
Here and , giving .
Quick check
(For , use the Bernoulli Chernoff calculation to bound . Give the expression exactly.)
Solution · Answer
Use , . The bound is . It applies to because .
Quick check
(An iid sample lies in . Find a number such that covers its mean with probability at least , for . Explain which probability is random.)
Solution · Answer
Set , obtaining . The interval varies with the sample, whereas the population mean is fixed. The coverage statement follows from the two-sided inequality; it does not assign probability to the fixed mean after observing a particular interval.