the Chernoff bound
/ CHER-nof /
Chebyshev tells you a deviation of many standard deviations is rare, but only at a leisurely 1/k^2 rate. For a sum of many independent coin-like contributions, reality is far more dramatic: the chance of a big deviation falls off exponentially, like e raised to a negative number. The Chernoff bound is the technique that captures this much sharper, exponentially small decay.
The trick is to apply Markov's inequality not to X, and not to X^2, but to the exponential e^(tX) for a tuning parameter t > 0. Because the exponential is increasing, the event X >= a is the same as e^(tX) >= e^(ta), and Markov gives P(X >= a) <= E[e^(tX)] / e^(ta). The quantity E[e^(tX)] is the moment generating function, M(t). Now comes the genius step: this holds for every t > 0, so you are free to pick the t that makes the right side smallest. Minimizing e^(-ta) M(t) over t squeezes out the tightest exponential bound the moments allow.
Why does this beat Chebyshev so badly? For a sum of n independent terms, the MGF of the sum is the product of the individual MGFs, so M(t) factorizes neatly and the bound becomes an exponential in n. That is the source of statements like 'the empirical average is within epsilon of the truth with probability at least 1 - 2 e^(-2 n epsilon^2)'. The honest catch: the method needs the MGF to exist near 0, which fails for heavy-tailed variables — there you fall back to Markov or Chebyshev. Hoeffding's and Bernstein's inequalities are just Chernoff's recipe carried out for specific, well-behaved cases.
Toss a fair coin n times; let X be the number of heads, mean n/2. Chernoff gives P(X >= 3n/4) <= e^(-n/8) roughly. For n = 100, that is about e^(-12.5), under 4 in a million — whereas Chebyshev would only promise about 1/25. The exponential decay is the whole point.
Markov applied to e^(tX), then optimized over t: exponentially small tails for sums.
Chernoff is not one formula but a method (Markov on the MGF, then optimize t). It only works where the MGF exists near 0; heavy-tailed variables have no MGF and resist this approach.