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
Entity-backed identity for the statement-form enum value this theorem already carries, resolved to a mathematics concept by an explicit value-to-entity map (phase 3 bucket conversion, docs\design_entity_backed_browse_buckets_20260928.md). The statement-form fact itself stays on the theorem unchanged.
In Branch
Source Chernoff bound (Wikipedia)
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.
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
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.