Back to course

Inequalities: Chernoff, Hoeffding, and More

Markov and Chebyshev give polynomial bounds and require almost nothing. When you additionally know the variables are independent and bounded, the bounds improve to exponential, and the improvement is dramatic.

Hoeffding's inequality

For independent X1,…,XnX_1,\ldots,X_n with Xi∈[ai,bi]X_i \in [a_i, b_i]:

Hoeffding's inequality
P(∑iXi−E[∑iXi]≥t)≤exp⁡(−2t2∑i(bi−ai)2)P\left(\sum_i X_i - E\left[\sum_i X_i\right] \geq t\right) \leq \exp\left(\frac{-2t^2}{\sum_i (b_i - a_i)^2}\right)

An exponential bound on how far a sum strays from its mean, and far tighter than Markov or Chebyshev where it applies.

The bound decays as e−t2e^{-t^2} rather than 1t2\frac{1}{t^2}. That difference is enormous in the tail.

Chernoff bounds

The Bernoulli specialisation. With X=∑iXiX = \sum_i X_i and μ=E[X]\mu = E[X], for δ>0\delta > 0:

P(X≥(1+δ)μ)≤exp⁡(−δ22+δμ)P\left(X \geq (1+\delta)\mu\right) \leq \exp\left(-\frac{\delta^2}{2+\delta}\mu\right)

and for 0<δ<10 < \delta < 1:

P(X≤(1−δ)μ)≤exp⁡(−δ22μ)P\left(X \leq (1-\delta)\mu\right) \leq \exp\left(-\frac{\delta^2}{2}\mu\right)

The comparison that makes the point

The rest of this lesson is for subscribers

Unlock every lesson in Advanced Topics in Probability and Statistics, and every other premium course.

Subscribe to continue

Test your knowledge

Questions are only available to subscribers.
Finish course

Keep reading Advanced Topics in Probability and Statistics

35 lessons in this course, and every other premium course, on one subscription.

Subscribe now
  • Every lesson in every course, with the worked examples and interactive simulators
  • Graded questions on every lesson, with explanations for the wrong answers as well as the right one
  • The trainers, timed assessments and brainteaser library that go with them