Herman Chernoff (1923-2026)

Herman Chernoff passed away on July 6, 5 days after turning 103. Ravi Boppana wrote a guest post about Chernoff's life for his 100th birthday. 

Let me talk about his most famous work, the Chernoff Bounds themselves.

If you have a coin that will be heads with probability \(p\), and you flip it \(n\) times, the expected number of heads is \(pn\). Informally Chernoff bounds says that for large \(n\) the number of heads will be quite close to \(pn\) with an exponentially small probability of being far away from \(pn\). For example, if you flip a coin with probability 30% chance of being heads 10,000 times, the probability that you will get at most 2500 heads is less than \(10^{-18}\).

More formally, for \(\delta \in (0,1)\), Chernoff's bound shows that

\[\Pr[|X - \mu| \geq \delta\mu] \leq 2e^{-\mu\delta^2/3}\]

for \(\mu = \mathbb{E}[X]\). I find the variation known as Hoeffding's inequality \[\Pr[|X - \mu| \geq t] \leq 2e^{-2t^2/n}\] easier to use for computational complexity.

Chernoff bounds play a major role in computational complexity, for example you can use Chernoff Bounds for probabilistic, quantum and interactive proof algorithms to reduce the error to exponentially small. That means using the union bound, a single random sequence will give the correct answer for all inputs, showing that BPP is in P/poly. 

Chernoff bounds are a key ingredient in the proof that MA (prover then verifier) is contained in AM (verifier then prover). Roughly you make the MA error so small that the same random coins work no matter what the prover might say. MA in AM plays a key role in the proof that NP in BPP implies PH in BPP which itself is necessary for Toda's theorem.

The proof of Chernoff bounds comes from a simple trick: Rather than bounding \(\Pr[X \geq a]\) directly via Markov's inequality on \(X\), you apply Markov to \(e^{tX}\) for a free parameter \(t > 0.\) Since \(e^{tX}\) is nonnegative,

\[\Pr[X \geq a] = \Pr[e^{tX} \geq e^{ta}] \leq \frac{\mathbb{E}[e^{tX}]}{e^{ta}},\]

and then you optimize over \(t\). The quantity \(\mathbb{E}[e^{tX}]\) is the moment generating function, and for a sum \(X = \sum_i X_i\) of independent variables it factorizes into \(\prod_i \mathbb{E}[e^{tX_i}]\). That factorization is what converts a linear tail bound into an exponential one, each independent term contributes multiplicatively, so the deviation probability shrinks like a product rather than a sum.

Chernoff did not think of himself as a theorist. 

People regard me as a theoretical statistician, but I’ve decided in recent years that I’m really an applied statistician. My theoretical insights have relied upon my work in thinking about applied problems.

A good lesson for us all.