Chernoff Bounds
Compare inclusive binomial tail probabilities with optimized Chernoff bounds, explore exponential tilts, and recognize trivial, deterministic and limiting cases.
Free theory articleCompare inclusive binomial tail probabilities with optimized Chernoff bounds, explore exponential tilts, and recognize trivial, deterministic and limiting cases.
Concept & interpretation
Suppose an event has probability p on each independent trial. How surprising is a large number of successes? We can add the relevant binomial probabilities to find the actual chance. A Chernoff bound instead gives a conservative guarantee by applying Markov’s inequality to an exponential. Exploring the gap between these answers shows both the strength and the limits of a probability bound.