The Chernoff Bound gives an exponentially decaying upper bound on the probability that a sum of independent random variables deviates from its expected value by a specified amount, derived by applying Markov's inequality to an exponential transform of the sum and then optimizing over the transform's free parameter. Named for Herman Chernoff, it is a standard concentration-of-measure tool, generally far sharper for large deviations than bounds obtained directly from Chebyshev's inequality.
Facts
StatementFor any t greater than zero, the probability that X is at least a is at most the infimum over t of the moment generating function of X evaluated at t, divided by e to the power t times a. 1 Classification
Statement Form Sources
1. Chernoff bound (Wikipedia)
Generic Chernoff bounds section
P(X >= a) <= inf over t > 0 of M(t) e^(-t a)
History section
The bound is commonly named after Herman Chernoff who described the method in a 1952 paper.
Lead section, statement-form reference
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.
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.