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 or exponential moments. 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). The Chernoff bound is especially useful for sums of independent random variables, such as sums of Bernoulli random variables. Despite being named after Herman Chernoff, the author of the paper it first appeared in, Chernoff attributes the result to Herman Rubin. 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 variates 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 variates 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. Generic Chernoff bounds 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 . Properties The exponential function is convex, so by Jensen's inequality . It follows that the bound on the right tail is trivially equal to 1 when ; similarly, the left bound is trivial for . We may therefore combine the two infima and define the two-sided Chernoff bound:which provides an upper bound on the folded cumulative distribution function of (folded at the mean, not the median). The logarithm of the two-sided Chernoff bound is known as the rate function (or Cramér transform) . It is equivalent to the Legendre–Fenchel transform or convex conjugate of the cumulant generating function , defined as: The moment generating function is increasing and log-convex, so by the properties of the convex conjugate, the Chernoff bound must be decreasing and log-concave. It attains its maximum at the mean,