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 Connections
Has Statement Form
In Branch
Source Chernoff bound (Wikipedia)
Proved By
Source Chernoff bound (Wikipedia)
Sources
1. Chernoff bound (Wikipedia)
Lead section
The bound is commonly named after Herman Chernoff who described the method in a 1952 paper, though Chernoff himself attributed it to Herman Rubin.
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.
In Branch: Probability and Statistics, Lead sentence
In probability theory, a Chernoff bound is an exponentially decreasing upper bound on the tail of a random variable based on its m
Proved By: Wassily Hoeffding, Lead
The following theorem is due to Wassily Hoeffding and hence is called the Chernoff-Hoeffding theorem
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.