Chernoff bound

A probabilistic inequality that bounds tail probabilities exponentially by applying Markov's inequality to an exponential transform, usually a moment-generating function.

Markov's inequality: For a nonnegative random variable, the probability it is at least a positive threshold is at most its expectation divided by that threshold. Applying it to an exponential transform produces the Chernoff bound.
Hoeffding's inequality: An exponential tail bound for sums of independent bounded random variables. It gives a readily applied concentration bound when each summand has a known range.
Hoeffding's lemma: A bound on the moment-generating function of a bounded random variable centered at its mean. It supplies the moment estimate that yields Hoeffding's inequality, a bounded-variable alternative.
Expected value: The probability-weighted average of a random variable's possible values. The deviation being bounded is measured relative to this central quantity.
Chernoff information: A measure of statistical distinguishability that determines an exponential error rate in hypothesis testing. It shares the Chernoff name and exponential-moment method, but addresses testing error rates.
Moment-generating function: A function that encodes a random variable's moments through the expectation of its exponential transform. Its values control the exponential tail estimate.
Chernoff–Hoeffding bound: A family of exponential tail bounds for sums of independent bounded random variables. This commonly used form specializes the method to bounded summands.
Bernstein inequality: A tail bound for sums of independent bounded random variables that uses variance and a bound on individual terms. Its variance-sensitive form can outperform a range-only estimate when variance is small.
Tail probability: The probability that a random variable lies beyond a specified threshold. Chernoff bounds provide upper estimates for these rare-event probabilities.
Large deviation theory: The study of exponentially small probabilities for rare events in probabilistic systems. Chernoff bounds are elementary tools for proving large-deviation estimates.

Linked from 10 pages