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…