Chernoff bound

In probability theory, a Chernoff bound is an exponentially decreasing upper bound on the tail of a random variable based on its moment generating function. The minimum of all such exponential bounds forms the Chernoff or Chernoff-Cramér bound, which may decay faster than exponential (e.g. sub-Gaussian). It is especially useful for sums of independent random variables, such as sums of Bernoulli random variables. The bound is commonly named after Herman Chernoff who described the method in a 1952 paper, though Chernoff himself attributed it to Herman Rubin. In 1938 Harald Cramér had published an almost identical concept now known as Cramér's theorem. It is a sharper bound than the first- or second-moment-based tail bounds such as Markov's inequality or Chebyshev's inequality, which only yield power-law bounds on tail decay. However, when applied to sums the Chernoff bound requires the random variables to be independent, a condition that is not required by either Markov's inequality or Chebyshev's inequality (although Chebyshev's inequality does require the random variables to be pairwise independent). The Chernoff bound is related to the Bernstein inequalities. It is also used to prove Hoeffding's inequality, Bennett's inequality, and McDiarmid's inequality. The generic Chernoff bound for a random variable is attained by applying Markov's inequality to (which is why it sometimes called the exponential Markov or exponential moments bound). For positive this gives a bound on the right tail of in terms of its moment-generating function : Since this bound holds for every positive , we may take the infimum: Performing the same analysis with negative we get a similar bound on the left tail: and The quantity can be expressed as the expectation value , or equivalently . The exponential function is convex, so by Jensen's inequality . It follows that the bound on the right tail is greater or equal to one when , and therefore trivial; similarly, the left bound is trivial for .