A Simple and Combinatorial Approach to Proving Chernoff Bounds and Their Generalizations

Abstract

The Chernoff bound is one of the most widely used tools in theoretical computer science. It's rare to find a randomized algorithm that doesn't employ a Chernoff bound in its analysis. The standard proofs of Chernoff bounds are beautiful but in some ways not very intuitive. In this paper, I'll show you a different proof that has four features: (1) the proof offers a strong intuition for why Chernoff bounds look the way that they do; (2) the proof is user-friendly and (almost) algebra-free; (3) the proof comes with matching lower bounds, up to constant factors in the exponent; and (4) the proof extends to establish generalizations of Chernoff bounds in other settings. The ultimate goal is that, once you know this proof (and with a bit of practice), you should be able to confidently reason about Chernoff-style bounds in your head, extending them to other settings, and convincing yourself that the bounds you're obtaining are tight (up to constant factors in the exponent).