# Chernoff bound

The Chernoff bound is an exponential upper bound on the tail probability of a random variable, obtained by applying [Markov's inequality](https://www.edgepedia.org/markovs-inequality) to the exponential random variable \( e^{tX} \) and then choosing the parameter \( t \) to make the resulting bound as small as possible<sup>[1](https://mathworld.wolfram.com/ChernoffBound.html)</sup>. The name does not refer to a single inequality but to a technique for obtaining exponentially decreasing bounds on tail probabilities, most famously for sums of independent random variables<sup>[2](https://crypto.stanford.edu/~blynn/pr/chernoff.html)</sup>. It is named for [Herman Chernoff](https://www.edgepedia.org/herman-chernoff), whose 1952 paper in the *Annals of Mathematical Statistics* developed the method in the context of hypothesis testing<sup>[3](https://cir.nii.ac.jp/crid/1571980075561167488)</sup>.

| Key fact | Detail |
|---|---|
| Core idea | Apply Markov's inequality to \( e^{tX} \), giving \( \Pr[X \ge a] \le \min_{t>0} e^{-ta} E[e^{tX}] \), where \( E[e^{tX}] \) is the moment generating function<sup>[1](https://mathworld.wolfram.com/ChernoffBound.html)</sup> |
| Multiplicative form (upper tail) | For independent 0/1 trials with \( E[\sum X_i] = \mu \): \( \Pr[X > (1+\epsilon)\mu] < \left[ \frac{e^{\epsilon}}{(1+\epsilon)^{(1+\epsilon)}} \right]^{\mu} \)<sup>[4](https://courses.csail.mit.edu/6.856/21/Notes/n6-chernoff.html)</sup> |
| Simple upper-tail forms | \( e^{-\mu\epsilon^2/(2+\epsilon)} \) for all \( \epsilon \); \( e^{-\mu\epsilon^2/3} \) for \( \epsilon < 1 \); \( e^{-\mu\epsilon^2/4} \) for \( \epsilon < 2e-1 \)<sup>[4](https://courses.csail.mit.edu/6.856/21/Notes/n6-chernoff.html)</sup> |
| Lower tail | \( \Pr[X < (1-\epsilon)\mu] < \left[ \frac{e^{-\epsilon}}{(1-\epsilon)^{(1-\epsilon)}} \right]^{\mu} \), bounded by \( e^{-\mu\epsilon^2/2} \)<sup>[4](https://courses.csail.mit.edu/6.856/21/Notes/n6-chernoff.html)</sup> |
| Dependence | The bound depends on \( \mu \), not on the number \( n \) of variables, and decays exponentially in \( \mu \)<sup>[4](https://courses.csail.mit.edu/6.856/21/Notes/n6-chernoff.html)</sup> |
| Origin | Herman Chernoff, *Annals of Mathematical Statistics* 23, 493–509 (1952); Stanford technical report SOL ONR 6, November 1951<sup>[3](https://cir.nii.ac.jp/crid/1571980075561167488)</sup><sup> • </sup><sup>[5](https://statistics.stanford.edu/technical-reports/measure-asymptotic-efficiency-tests-hypothesis-based-sum-observations)</sup> |

## The general method

The starting point is Markov's inequality, which states that a non-negative random variable \( X \) satisfies \( \Pr[X \ge a] \le E(X)/a \)<sup>[6](https://math.mit.edu/~goemans/18310S15/chernoff-notes.pdf)</sup>. Because \( e^{tx} \) is increasing and non-negative for \( t > 0 \), the events \( X \ge c \) and \( e^{tX} \ge e^{tc} \) coincide, and Markov's inequality gives

\[ \Pr[X \ge c] \le \frac{E(e^{tX})}{e^{tc}} = M_X(t)e^{-tc}, \]

where \( M_X(t) = E(e^{tX}) \) is the moment generating function of \( X \)<sup>[7](https://data140.org/textbook/content/chapter-19/chernoff-bound/)</sup>. Since \( t \) can be any positive number, the sharpest bound is the optimized form

\[ \Pr[X \ge c] \le \min_{t > 0} M_X(t)e^{-tc}. \]

Applying the same argument to \( -X \) yields a bound on the lower tail<sup>[1](https://mathworld.wolfram.com/ChernoffBound.html)</sup>. The method requires the moment generating function to be finite for the chosen \( t \); it fails for heavy-tailed distributions such as the Cauchy, which has no finite moments at all<sup>[8](https://theorempath.com/topics/chernoff-bounds)</sup>.

**Why independence matters.** For a sum \( X = X_1 + \cdots + X_N \) of independent variables, the moment generating function factors into a product, \( M_X(t) = \prod_i M_{X_i}(t) \), which is what makes the bound especially useful for showing that sums are exponentially unlikely to differ greatly from their expectations<sup>[1](https://mathworld.wolfram.com/ChernoffBound.html)</sup>. The bounds generally take the form \( e^{-r(n)\epsilon^2} \) with rate \( r(n) \) of order \( n \)<sup>[9](https://www.stat.cmu.edu/~cshalizi/sml/21/lectures/05/lecture-05.html)</sup>.

## The multiplicative Chernoff bound

The most used form applies to sums of independent Bernoulli trials, sometimes called Poisson trials when the success probabilities \( p_i \) differ. Let \( X = \sum_{i=1}^N X_i \), where \( X_i \) equals 1 with probability \( p_i \) and 0 otherwise, and let \( \mu = E[X] = \sum_i p_i \)<sup>[2](https://crypto.stanford.edu/~blynn/pr/chernoff.html)</sup>. For \( \epsilon > 0 \),

\[ \Pr[X > (1+\epsilon)\mu] < \left[ \frac{e^{\epsilon}}{(1+\epsilon)^{(1+\epsilon)}} \right]^{\mu}. \]

The bound is independent of \( n \) and exponential in \( \mu \) with base less than 1<sup>[4](https://courses.csail.mit.edu/6.856/21/Notes/n6-chernoff.html)</sup>. The proof applies Markov's inequality to \( e^{tX} \), uses independence to write \( E[e^{tX}] = \prod_i E[e^{tX_i}] \), bounds each factor using \( 1 + p_i(e^t - 1) \le e^{p_i(e^t-1)} \), and minimizes over \( t \); the optimum is \( t = \ln(1+\epsilon) \)<sup>[4](https://courses.csail.mit.edu/6.856/21/Notes/n6-chernoff.html)</sup><sup> • </sup><sup>[2](https://crypto.stanford.edu/~blynn/pr/chernoff.html)</sup>.

Because the exact form is awkward to use, cruder but friendlier approximations are standard<sup>[2](https://crypto.stanford.edu/~blynn/pr/chernoff.html)</sup>:

- \( \Pr[X > (1+\epsilon)\mu] < e^{-\mu\epsilon^2/(2+\epsilon)} \) for all \( \epsilon \);
- \( \Pr[X > (1+\epsilon)\mu] < e^{-\mu\epsilon^2/3} \) for \( \epsilon < 1 \);
- \( \Pr[X > (1+\epsilon)\mu] < e^{-\mu\epsilon^2/4} \) for \( \epsilon < 2e-1 \);
- \( \Pr[X > (1+\epsilon)\mu] < 2^{-(1+\epsilon)\mu} \) for larger \( \epsilon \)<sup>[4](https://courses.csail.mit.edu/6.856/21/Notes/n6-chernoff.html)</sup>.

The same argument applied to \( e^{-tX} \) bounds the lower tail, \( \Pr[X < (1-\epsilon)\mu] < \left[ \frac{e^{-\epsilon}}{(1-\epsilon)^{(1-\epsilon)}} \right]^{\mu} \), which is in turn bounded by \( e^{-\mu\epsilon^2/2} \)<sup>[4](https://courses.csail.mit.edu/6.856/21/Notes/n6-chernoff.html)</sup>.

**Scope of the bound.** The bound generalizes to any variables distributed in the range \( [0,1] \), not only 0/1 trials<sup>[4](https://courses.csail.mit.edu/6.856/21/Notes/n6-chernoff.html)</sup>. Compared with [Hoeffding's inequality](https://www.edgepedia.org/hoeffdings-inequality), Chernoff gives a good bound as long as \( E[X] \) is large and does not care how many variables there are, while Hoeffding usually has better constant factors and applies when variables may be negative or positive<sup>[10](https://www.cs.cornell.edu/courses/cs4850/2025sp/notes/2025-02-10.pdf)</sup>.

## How sharp the bound is

The bound trails off when \( \epsilon \approx 1/\sqrt{\mu} \), that is, at an absolute error of about \( \sqrt{\mu} \), which is expected since the standard deviation of the sum is around \( \sqrt{\mu} \)<sup>[4](https://courses.csail.mit.edu/6.856/21/Notes/n6-chernoff.html)</sup>. If \( \mu = \Omega(\log n) \), the probability of a constant \( \epsilon \) deviation is \( O(1/n) \), which is useful when a polynomial number of events must all hold simultaneously<sup>[4](https://courses.csail.mit.edu/6.856/21/Notes/n6-chernoff.html)</sup>.

For a Gaussian random variable with variance \( \sigma^2 \), minimizing \( e^{-tc + \sigma^2 t^2/2} \) over \( t \) gives \( \Pr[X - \mu \ge c] \le e^{-c^2/(2\sigma^2)} \), matching the exponent of the exact tail<sup>[9](https://www.stat.cmu.edu/~cshalizi/sml/21/lectures/05/lecture-05.html)</sup><sup> • </sup><sup>[7](https://data140.org/textbook/content/chapter-19/chernoff-bound/)</sup>. Distributions whose centered moment generating function satisfies \( M_X(t) \le e^{t^2 c^2/2} \) are called sub-Gaussian, and they inherit the same \( e^{-n\epsilon^2/(2c^2)} \) bound for sample averages<sup>[9](https://www.stat.cmu.edu/~cshalizi/sml/21/lectures/05/lecture-05.html)</sup>.

## Chernoff versus Hoeffding

For i.i.d. Bernoulli variables with \( X_i \sim \mathrm{Ber}(p) \) and \( \mu = np \), Hoeffding's inequality gives \( \Pr[|X - \mu| \ge \delta\mu] \le 2\exp(-2\delta^2 p^2 n) \), while the Chernoff bound gives \( 2\exp(-\tfrac{1}{3}\delta^2 p n) \)<sup>[11](https://jhc.sjtu.edu.cn/~kuanyang/teaching/CS3341/notes/lec05.pdf)</sup>. For \( p > 1/6 \), Hoeffding's inequality is tighter up to a constant factor; for smaller \( p \), the Chernoff bound is significantly better because its dependence on \( p \) is linear rather than quadratic<sup>[11](https://jhc.sjtu.edu.cn/~kuanyang/teaching/CS3341/notes/lec05.pdf)</sup>. In a sampling example where a fraction \( p \) of balls in a box are red, estimating \( p \) within a factor of \( 1 \pm 0.01 \) requires \( \Omega(1/p) \) draws using the Chernoff bound but \( \Omega(1/p^2) \) using Hoeffding's inequality<sup>[11](https://jhc.sjtu.edu.cn/~kuanyang/teaching/CS3341/notes/lec05.pdf)</sup>. Hoeffding's 1963 paper contains a comparison of the bounds<sup>[12](https://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15850-f18/www/)</sup>.

## History

Herman Chernoff published "A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the Sum of Observations" in the *Annals of Mathematical Statistics* in 1952 (volume 23, pages 493–509); a Stanford technical report version, SOL ONR 6, is dated November 1951<sup>[3](https://cir.nii.ac.jp/crid/1571980075561167488)</sup><sup> • </sup><sup>[5](https://statistics.stanford.edu/technical-reports/measure-asymptotic-efficiency-tests-hypothesis-based-sum-observations)</sup>. Chernoff himself attributed the proof of the bound to Herman Rubin<sup>[12](https://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15850-f18/www/)</sup>. N. Bernstein<sup>[13](https://imechanica.egr.uh.edu/sites/default/files/ConcOfMeasure_master.pdf)</sup>. A 2025 survey collects the original bounds of the seminal Chernoff and Hoeffding papers together with derivative bounds in a variety of forms<sup>[14](https://arxiv.org/abs/2506.15612)</sup>.

## Applications

The bound is a standard tool in the analysis of randomized algorithms. Course treatments apply it to load balancing, where Chernoff bounds with \( \delta = c - 1 \) combined with a union bound show that with probability at least \( 1 - 1/n \) no processor receives more than a constant multiple of the average load<sup>[15](https://fanchung.ucsd.edu/teach/202/14/13RandomizedAlgorithms.pdf)</sup>, to set balancing<sup>[11](https://jhc.sjtu.edu.cn/~kuanyang/teaching/CS3341/notes/lec05.pdf)</sup>, and to coupon collecting and statistical estimation<sup>[16](https://people.cs.umass.edu/~cmusco/CS614S24/schedule.html)</sup>. A related Poisson tail bound states that for a Poisson random variable with rate \( \lambda \), \( \Pr[X \ge t] \le e^{-\lambda}(e\lambda/t)^t \) for \( t > \lambda \)<sup>[11](https://jhc.sjtu.edu.cn/~kuanyang/teaching/CS3341/notes/lec05.pdf)</sup>. The technique has also been extended beyond independent sums, for example to optimal Chernoff-type bounds for large deviations of sums of functions of finite-state Markov chains<sup>[17](https://arxiv.org/abs/1907.04467)</sup>.

## References

1. [Chernoff Bound, Wolfram MathWorld](https://mathworld.wolfram.com/ChernoffBound.html)
2. [The Chernoff Bound, Stanford University (B. Lynn)](https://crypto.stanford.edu/~blynn/pr/chernoff.html)
3. [A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations, CiNii Research](https://cir.nii.ac.jp/crid/1571980075561167488)
4. [6.856 Lecture Notes: Chernoff Bound, MIT CSAIL](https://courses.csail.mit.edu/6.856/21/Notes/n6-chernoff.html)
5. [A Measure of Asymptotic Efficiency for Tests of an Hypothesis Based on the Sum of Observations, Stanford Department of Statistics](https://statistics.stanford.edu/technical-reports/measure-asymptotic-efficiency-tests-hypothesis-based-sum-observations)
6. [Chernoff bounds, and some applications (M. Goemans, MIT 18.310 lecture notes)](https://math.mit.edu/~goemans/18310S15/chernoff-notes.pdf)
7. [Chernoff Bound, Data 140 Textbook, UC Berkeley](https://data140.org/textbook/content/chapter-19/chernoff-bound/)
8. [Chernoff Bounds, TheoremPath](https://theorempath.com/topics/chernoff-bounds)
9. [Deviation Bounds I: Markov Inequality etc. (C. Shalizi, CMU lecture notes)](https://www.stat.cmu.edu/~cshalizi/sml/21/lectures/05/lecture-05.html)
10. [Summary: Chernoff and Hoeffding deliver similar results, Cornell CS 4850 notes](https://www.cs.cornell.edu/courses/cs4850/2025sp/notes/2025-02-10.pdf)
11. [CS3341 Lecture 5 notes, Shanghai Jiao Tong University (K. Yang)](https://jhc.sjtu.edu.cn/~kuanyang/teaching/CS3341/notes/lec05.pdf)
12. [15-850: CMU Advanced Algorithms, Fall 2018](https://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15850-f18/www/)
13. [Concentration of Measure lecture notes, University of Houston](https://imechanica.egr.uh.edu/sites/default/files/ConcOfMeasure_master.pdf)
14. [A survey of Chernoff and Hoeffding bounds (A. V. Gerbessiotis, arXiv 2025)](https://arxiv.org/abs/2506.15612)
15. [Randomized Algorithms lecture notes, UC San Diego (F. Chung)](https://fanchung.ucsd.edu/teach/202/14/13RandomizedAlgorithms.pdf)
16. [COMPSCI 614: Randomized Algorithms with Applications to Data Science, UMass Amherst](https://people.cs.umass.edu/~cmusco/CS614S24/schedule.html)
17. [Optimal Chernoff and Hoeffding Bounds for Finite State Markov Chains, arXiv](https://arxiv.org/abs/1907.04467)

---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Statistics and probability › Probability theory › Expectation, moments, and inequalities › Exponential and Chernoff-type bounds*

*Initially written Sep 17, 2026 · Reviewed: Sep 30, 2026; Oct 15, 2026 · Edited: Oct 15, 2026 · Last review: Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license