Lesson 7

Informally, such inequalities state that the sum of mutually independent random variables exceeds its expectation by a factor of \(\varepsilon\) with exponentially small probability.

Let's start with a special case formulation, the frequency of heads when flipping a fair coin. We will leave it without proof.

Theorem (Chernoff, 1952). Let \(\alpha\) be the frequency of heads among \(n\) flips of a fair coin. Then \[\Pr\left[\left|\alpha-\frac{1}{2}\right| \ge \varepsilon \right] \le 2e^{-2\varepsilon^2n}\ .\]

It is clear that this bound is much stronger than the bound \(\frac{4}{n}\), which we previously derived from Chebyshev’s inequality. Another way to compare the two bounds: Chebyshev’s inequality tells us that \(\alpha\) deviates from its mean by at least \(1/4\) with probability at most \(4/n\). Meanwhile, Chernoff’s inequality states that even for \(\varepsilon=\sqrt{\ln n/(2n)}\) (which is much smaller than \(1/4\)), the deviation occurs with probability no greater than \(4/n\).