Concentration Inequalities

How likely is a fair coin, tossed a million times, to land heads at least 51% of the time? A crude bound from Markov and Chebyshev Inequalities says the probability is at most about 10−210^{-2}. The truth is smaller than 10−8710^{-87}. This gap is not a curiosity. It is the difference between an inequality that is merely true and one that is useful. Closing that gap is the subject of concentration inequalities. Concentration inequalities quantify a single intuitive phenomenon. A sum of many independent, weakly-behaved random variables is astonishingly unlikely to stray far from its mean. Chebyshev's inequality already tells us this. But it only offers a polynomial rate in the deviation. The insight that upgrades polynomial control to exponential control is the Chernoff bound. Instead of bounding P(X≥a)\mathbb{P}(X \geq a) by controlling moments of XX, one controls the moment generating function E[etX]\mathbb{E}[e^{tX}]. One then optimizes over the auxiliary parameter tt. For sums of independent bounded random variables, this optimization can be carried out explicitly. This yields Hoeffding's inequality, one of the most quoted results in probability, statistics, and learning theory. The payoff is enormous. The Central Limit Theorem tells us that Xˉn\bar X_n is approximately Gaussian for large nn. Chebyshev gives a bound that decays like 1/n1/n. Chernoff–Hoeffding gives a bound decaying like e−cne^{-cn} instead. This bound is valid for every nn, not just asymptotically. It requires no distributional assumption beyond boundedness. This non-asymptotic, distribution-free exponential decay is exactly what modern statistics needs. Randomized algorithms and machine learning theory need it too. They need finite-sample guarantees that hold with overwhelming probability after a modest number of trials. This article develops the machinery from first principles. We derive the general Chernoff technique. We prove Hoeffding's Lemma, the key sub-Gaussian bound on bounded mean-zero variables. We assemble Hoeffding's inequality for sums and averages. We work two asymmetric numerical examples. Finally, we show precisely where boundedness cannot be dropped.

Key takeaways
  • Markov/Chebyshev give polynomial tail bounds; Chernoff bounds exploit E[etX]\mathbb{E}[e^{tX}] to get exponential tail bounds.
  • The Chernoff bound is P(X≥a)≤inf⁡t>0e−taE[etX]\mathbb{P}(X\geq a)\le \inf_{t>0} e^{-ta}\mathbb{E}[e^{tX}], valid for any real random variable and any aa.
  • Hoeffding's Lemma bounds the MGF of any mean-zero variable confined to [a,b][a,b] by a Gaussian-type MGF with variance proxy (b−a)2/4(b-a)^2/4.
  • Hoeffding's Inequality gives P(∣Xˉn−μ∣≥ε)≤2exp⁡ ⁣(−2n2ε2∑(bi−ai)2)\mathbb{P}(|\bar X_n - \mu| \ge \varepsilon) \le 2\exp\!\left(-\frac{2n^2\varepsilon^2}{\sum (b_i-a_i)^2}\right) for independent bounded summands.
  • Unlike Chebyshev's O(1/n)O(1/n) decay, this bound decays exponentially in nn, and needs no assumption on higher moments or on the underlying distribution.
  • Key idea: optimize an exponential tilt etXe^{tX} over tt instead of using a fixed power, converting Markov's crude polynomial control into a sharp exponential one.

Where this lives today

Chernoff–Hoeffding bounds are the workhorse of randomized algorithm analysis: to show a randomized algorithm succeeds with high probability after repeated independent trials (e.g. randomized primality testing, Monte Carlo estimation, load balancing), one directly applies Hoeffding-type bounds to certify exponentially small failure probability as the number of trials grows. In statistical learning theory, Hoeffding's inequality underlies PAC (Probably Approximately Correct) learning bounds: the empirical risk of a classifier concentrates exponentially around its true risk, which is what makes finite training-sample generalization guarantees possible. Coupled with a union bound over a finite (or VC-dimension-controlled) hypothesis class, this yields the classical sample-complexity bounds of statistical learning theory. In cryptography, concentration bounds certify that adversarial guessing strategies or key-recovery attacks succeed with negligible probability, and they justify the security parameters chosen for randomized protocols. In statistics, Hoeffding-type inequalities give non-asymptotic confidence intervals for bounded data (e.g. proportions, bounded scores, ratings) that are valid at every sample size nn, unlike the asymptotic normal-approximation intervals derived from the Central Limit Theorem, which are only guaranteed accurate as n→∞n \to \infty. In physics and engineering, related large-deviation techniques (Cramér's theorem, of which the Chernoff bound is the elementary precursor) describe rare-event probabilities in statistical mechanics, queueing theory, and information theory (e.g. bounding decoding error probabilities in channel coding).

:::quiz[In Hoeffding's Lemma, a mean-zero variable supported on [a,b][a,b] is shown to be sub-Gaussian with variance proxy]

  • (b−a)2(b-a)^2
  • (b−a)2/4(b-a)^2/4 ✓
  • (b2−a2)/2(b^2-a^2)/2
  • b−ab - a

:::faq[Does Hoeffding's inequality require symmetric intervals like [−c,c][-c,c]?] No. The interval [ai,bi][a_i,b_i] for each XiX_i can be any bounded interval, not necessarily symmetric about 00 or about the mean. The bound depends only on the length bi−aib_i - a_i, not on the location of the interval; shifting a variable by a constant does not change its range length and leaves the Hoeffding bound unchanged, consistent with the proof's use of the mean-zero centered variable Yi=Xi−E[Xi]Y_i = X_i - \mathbb{E}[X_i].

Ask the tutor: How does the Chernoff–Hoeffding technique generalize to martingale differences via the Azuma–Hoeffding inequality?

DefinitionMoment Generating Function and Sub-Gaussian Variable

Let XX be a real random variable. Its moment generating function (MGF) is

MX(t)=E[etX],t∈R,M_X(t) = \mathbb{E}[e^{tX}], \qquad t \in \mathbb{R},

whenever this expectation is finite. A random variable XX with E[X]=0\mathbb{E}[X]=0 is called sub-Gaussian with variance proxy σ2\sigma^2 if

MX(t)≤exp⁡ ⁣(σ2t22)for all t∈R.M_X(t) \le \exp\!\left(\frac{\sigma^2 t^2}{2}\right) \qquad \text{for all } t \in \mathbb{R}.

This is precisely the MGF bound satisfied by a mean-zero Gaussian random variable N(0,σ2)N(0,\sigma^2), whose MGF equals exp⁡(σ2t2/2)\exp(\sigma^2t^2/2) exactly. Sub-Gaussianity says XX's tails are no heavier than a Gaussian's, even if XX is far from Gaussian in distribution (for instance, if XX is bounded or discrete).

Intuition

Markov's inequality bounds P(X≥a)\mathbb{P}(X \ge a) using only E[X]\mathbb{E}[X]; Chebyshev upgrades this using Var(X)\mathrm{Var}(X), i.e. the second moment of a centered variable. The natural next step is to use all moments simultaneously — and the object that packages every moment at once is the moment generating function, since MX(t)=∑ktkk!E[Xk]M_X(t) = \sum_k \frac{t^k}{k!}\mathbb{E}[X^k]. Applying Markov's inequality not to XX but to the tilted, strictly increasing transform etXe^{tX} for a well-chosen t>0t>0 converts a tail event {X≥a}\{X \ge a\} into {etX≥eta}\{e^{tX} \ge e^{ta}\}, and Markov applied there gives a bound involving MX(t)/etaM_X(t)/e^{ta}. Because this holds for every t>0t>0, we may minimize over tt, and this single extra degree of freedom is what produces exponential rather than polynomial decay. For sums of independent variables, MGFs multiply: MSn(t)=∏iMXi(t)M_{S_n}(t) = \prod_i M_{X_i}(t), turning a sum into a product and letting the bound compound across all nn terms — this multiplicativity is the structural reason the tail probability ends up exponentially small in nn. Hoeffding's contribution is a clean, universal bound on the MGF of any bounded mean-zero variable (Hoeffding's Lemma), which converts "boundedness" into "sub-Gaussianity," after which the Chernoff machine runs automatically.

Figure
The Chernoff optimization: minimizing e−taMX(t)e^{-ta}M_X(t) over t>0t>0
t bound e^(-ta) M_X(t) t* (optimal tilt) min value = Chernoff bound
TheoremChernoff Bound

Let XX be a real random variable such that MX(t)=E[etX]M_X(t) = \mathbb{E}[e^{tX}] is finite for tt in some open interval containing 00. Then for every real number aa,

P(X≥a)  ≤  inf⁡t>0 e−ta MX(t),\mathbb{P}(X \ge a) \;\le\; \inf_{t > 0} \, e^{-ta}\, M_X(t),

and symmetrically, for every real aa,

P(X≤a)  ≤  inf⁡t<0 e−ta MX(t).\mathbb{P}(X \le a) \;\le\; \inf_{t < 0} \, e^{-ta}\, M_X(t).
Proof

Technique: Markov's inequality applied to an exponential transform. Fix t>0t>0 for which MX(t)<∞M_X(t)<\infty. The function x↦etxx \mapsto e^{tx} is strictly increasing on R\mathbb{R} since t>0t>0, so the events {X≥a}\{X \ge a\} and {etX≥eta}\{e^{tX} \ge e^{ta}\} are identical:

X≥a  ⟺  tX≥ta  ⟺  etX≥eta.X \ge a \iff tX \ge ta \iff e^{tX} \ge e^{ta}.

Hence P(X≥a)=P(etX≥eta)\mathbb{P}(X \ge a) = \mathbb{P}(e^{tX} \ge e^{ta}). The random variable Y:=etXY := e^{tX} is non-negative, so Markov and Chebyshev Inequalities (Markov's inequality) applies directly to YY with threshold eta>0e^{ta} > 0:

P(Y≥eta)≤E[Y]eta=MX(t)eta=e−taMX(t).\mathbb{P}(Y \ge e^{ta}) \le \frac{\mathbb{E}[Y]}{e^{ta}} = \frac{M_X(t)}{e^{ta}} = e^{-ta} M_X(t).

This chain of (in)equalities holds for the fixed t>0t>0 we chose, but t>0t>0 was arbitrary among values where MX(t)M_X(t) is finite. Since the left side P(X≥a)\mathbb{P}(X\ge a) does not depend on tt, we may take the infimum of the right side over all valid t>0t>0 without affecting the validity of the bound on the left:

P(X≥a)≤inf⁡t>0e−taMX(t).\mathbb{P}(X \ge a) \le \inf_{t>0} e^{-ta} M_X(t).

For the second claim, fix t<0t<0. Then x↦etxx\mapsto e^{tx} is strictly decreasing, so {X≤a}={tX≥ta}={etX≥eta}\{X \le a\} = \{tX \ge ta\} = \{e^{tX}\ge e^{ta}\}, and the identical Markov argument applied to Y=etXY=e^{tX} with threshold etae^{ta} gives P(X≤a)≤e−taMX(t)\mathbb{P}(X\le a) \le e^{-ta}M_X(t) for this tt; taking the infimum over t<0t<0 completes the proof. ■\blacksquare

∎
LemmaHoeffding's Lemma

Let XX be a random variable with E[X]=0\mathbb{E}[X] = 0 and P(X∈[a,b])=1\mathbb{P}(X \in [a,b]) = 1 for real numbers a<ba < b. Then for every t∈Rt \in \mathbb{R},

E[etX]  ≤  exp⁡ ⁣(t2(b−a)28).\mathbb{E}[e^{tX}] \;\le\; \exp\!\left(\frac{t^2(b-a)^2}{8}\right).

Equivalently, XX is sub-Gaussian with variance proxy σ2=(b−a)2/4\sigma^2 = (b-a)^2/4.

Proof

Technique: convexity bound + Taylor expansion with a variational (max-variance) step. Fix t∈Rt \in \mathbb{R}; the case t=0t = 0 is trivial (1≤11 \le 1), so assume t≠0t \ne 0. Since a≤X≤ba \le X \le b almost surely, write XX as a convex combination of the endpoints: for λ(X):=X−ab−a∈[0,1]\lambda(X) := \frac{X-a}{b-a} \in [0,1],

X=λ(X) b+(1−λ(X)) a.X = \lambda(X)\, b + (1-\lambda(X))\, a.

Because x↦etxx \mapsto e^{tx} is convex, applying convexity pointwise (not the expectation yet) gives

etX≤λ(X) etb+(1−λ(X)) etaalmost surely.e^{tX} \le \lambda(X)\, e^{tb} + (1-\lambda(X))\, e^{ta} \qquad \text{almost surely}.

Taking expectations (linearity, and using E[λ(X)]=E[X]−ab−a=−ab−a\mathbb{E}[\lambda(X)] = \frac{\mathbb{E}[X]-a}{b-a} = \frac{-a}{b-a} since E[X]=0\mathbb{E}[X]=0), and writing p:=−ab−a∈[0,1]p := \frac{-a}{b-a} \in [0,1] (note 1−p=bb−a1-p = \frac{b}{b-a}), we get

E[etX]≤p etb+(1−p) eta.\mathbb{E}[e^{tX}] \le p\, e^{tb} + (1-p)\, e^{ta}.

Set u=t(b−a)u = t(b-a) and factor out etae^{ta}:

p etb+(1−p) eta=eta(p et(b−a)+(1−p))=eta(1−p+peu).p\,e^{tb} + (1-p)\,e^{ta} = e^{ta}\left(p\, e^{t(b-a)} + (1-p)\right) = e^{ta}\left(1 - p + p e^{u}\right).

Define L(u):=log⁡(1−p+peu)+ta=−pu+log⁡(1−p+peu)L(u) := \log\big(1 - p + p e^u\big) + ta = -pu + \log(1-p+pe^u), using ta=−puta = -pu (since p=−a/(b−a)p = -a/(b-a) and u=t(b−a)u=t(b-a) gives pu=−atpu = -a t). We must show

L(u)≤u28.L(u) \le \frac{u^2}{8}.

Compute derivatives in uu. Let g(u)=log⁡(1−p+peu)g(u) = \log(1-p+pe^u), so L(u)=g(u)−puL(u) = g(u) - pu. Then

g′(u)=peu1−p+peu,L′(u)=g′(u)−p.g'(u) = \frac{p e^u}{1-p+pe^u}, \qquad L'(u) = g'(u) - p.

Note L(0)=g(0)−0=log⁡(1)=0L(0) = g(0) - 0 = \log(1) = 0, and L′(0)=p1−p+p−p=p−p=0L'(0) = \frac{p}{1-p+p} - p = p - p = 0. Now compute the second derivative:

g′′(u)=peu(1−p+peu)−peu⋅peu(1−p+peu)2=peu(1−p)(1−p+peu)2.g''(u) = \frac{p e^u (1-p+pe^u) - p e^u \cdot p e^u}{(1-p+pe^u)^2} = \frac{p e^u(1-p)}{(1-p+pe^u)^2}.

Let q(u):=peu1−p+peu∈(0,1)q(u) := \frac{pe^u}{1-p+pe^u} \in (0,1) (this is g′(u)g'(u), a probability-like weight). Then g′′(u)=q(u)(1−q(u))g''(u) = q(u)(1-q(u)). Since q(1−q)≤1/4q(1-q) \le 1/4 for all q∈[0,1]q\in[0,1] (as q(1−q)q(1-q) is maximized at q=1/2q=1/2 with value 1/41/4, by elementary calculus on the quadratic q−q2q - q^2), we get

L′′(u)=g′′(u)≤14for all u.L''(u) = g''(u) \le \frac{1}{4} \qquad \text{for all } u.

By Taylor's theorem with the Lagrange remainder, for some ξ\xi between 00 and uu,

L(u)=L(0)+L′(0)u+L′′(ξ)2u2=0+0+L′′(ξ)2u2≤u28.L(u) = L(0) + L'(0) u + \frac{L''(\xi)}{2} u^2 = 0 + 0 + \frac{L''(\xi)}{2}u^2 \le \frac{u^2}{8}.

Therefore E[etX]≤etaexp⁡(1−p+peu terms)=exp⁡(L(u)+ta−ta)\mathbb{E}[e^{tX}] \le e^{ta}\exp(1-p+pe^u \text{ terms})=\exp(L(u)+ta - ta); unwinding, log⁡E[etX]≤log⁡(eta(1−p+peu))=ta+g(u)=L(u)≤u2/8=t2(b−a)28\log \mathbb{E}[e^{tX}] \le \log(e^{ta}(1-p+pe^u)) = ta + g(u)= L(u) \le u^2/8 = \frac{t^2(b-a)^2}{8}. Exponentiating gives the claimed bound. ■\blacksquare

∎
TheoremHoeffding's Inequality

Let X1,…,XnX_1, \dots, X_n be independent random variables such that, for each ii, XiX_i takes values in a bounded interval [ai,bi][a_i, b_i] almost surely (with ai<bia_i < b_i). Let Sn=∑i=1nXiS_n = \sum_{i=1}^n X_i and μ=E[Sn]=∑iE[Xi]\mu = \mathbb{E}[S_n] = \sum_i \mathbb{E}[X_i]. Then for every ε>0\varepsilon > 0,

P(Sn−μ≥ε)  ≤  exp⁡ ⁣(−2ε2∑i=1n(bi−ai)2),\mathbb{P}(S_n - \mu \ge \varepsilon) \;\le\; \exp\!\left(-\frac{2\varepsilon^2}{\sum_{i=1}^n (b_i-a_i)^2}\right),

and, by the same bound applied to −Sn-S_n,

P(∣Sn−μ∣≥ε)  ≤  2exp⁡ ⁣(−2ε2∑i=1n(bi−ai)2).\mathbb{P}(|S_n - \mu| \ge \varepsilon) \;\le\; 2\exp\!\left(-\frac{2\varepsilon^2}{\sum_{i=1}^n (b_i-a_i)^2}\right).

In particular, if Xˉn=Sn/n\bar X_n = S_n/n and μ0=E[Xˉn]\mu_0 = \mathbb{E}[\bar X_n], then for every ε>0\varepsilon>0,

P(∣Xˉn−μ0∣≥ε)  ≤  2exp⁡ ⁣(−2n2ε2∑i=1n(bi−ai)2).\mathbb{P}(|\bar X_n - \mu_0| \ge \varepsilon) \;\le\; 2\exp\!\left(-\frac{2n^2\varepsilon^2}{\sum_{i=1}^n(b_i-a_i)^2}\right).
Proof

Technique: Chernoff bound + Hoeffding's Lemma + independence (MGF multiplicativity). Let Yi:=Xi−E[Xi]Y_i := X_i - \mathbb{E}[X_i], so E[Yi]=0\mathbb{E}[Y_i]=0 and Yi∈[ai−E[Xi], bi−E[Xi]]Y_i \in [a_i - \mathbb{E}[X_i],\, b_i - \mathbb{E}[X_i]] almost surely, an interval of the same length bi−aib_i - a_i. Let Tn:=∑iYi=Sn−μT_n := \sum_i Y_i = S_n - \mu.

Step 1 (MGF of TnT_n via independence). Since X1,…,XnX_1,\dots,X_n are independent, so are Y1,…,YnY_1,\dots,Y_n (each YiY_i is a fixed function of XiX_i alone). For independent random variables, the MGF of the sum is the product of the MGFs: for any tt such that each MYi(t)M_{Y_i}(t) is finite,

MTn(t)=E[exp⁡(t∑iYi)]=E[∏ietYi]=∏iE[etYi],M_{T_n}(t) = \mathbb{E}\left[\exp\Big(t\sum_i Y_i\Big)\right] = \mathbb{E}\left[\prod_i e^{tY_i}\right] = \prod_i \mathbb{E}[e^{tY_i}],

where the last equality uses independence of the YiY_i (expectation of a product of independent random variables is the product of expectations — itself a direct consequence of independence of the underlying σ\sigma-algebras, applied to the measurable functions etYie^{tY_i}). Each factor here is finite because YiY_i is bounded, so etYie^{tY_i} is bounded, hence integrable.

Step 2 (bound each factor by Hoeffding's Lemma). By Hoeffding's Lemma applied to each YiY_i (mean zero, supported on an interval of length bi−aib_i - a_i),

MYi(t)≤exp⁡ ⁣(t2(bi−ai)28).M_{Y_i}(t) \le \exp\!\left(\frac{t^2(b_i-a_i)^2}{8}\right).

Multiplying across i=1,…,ni=1,\dots,n,

MTn(t)≤exp⁡ ⁣(t28∑i=1n(bi−ai)2)=:exp⁡(t2σ2/2),where σ2:=14∑i(bi−ai)2.M_{T_n}(t) \le \exp\!\left(\frac{t^2}{8}\sum_{i=1}^n (b_i-a_i)^2\right) =: \exp(t^2 \sigma^2/2), \quad \text{where } \sigma^2 := \frac{1}{4}\sum_i (b_i - a_i)^2.

Step 3 (Chernoff optimization). By the Chernoff Bound applied to TnT_n with threshold ε>0\varepsilon > 0,

P(Tn≥ε)≤inf⁡t>0e−tεMTn(t)≤inf⁡t>0exp⁡ ⁣(−tε+t2σ22).\mathbb{P}(T_n \ge \varepsilon) \le \inf_{t>0} e^{-t\varepsilon} M_{T_n}(t) \le \inf_{t>0} \exp\!\left(-t\varepsilon + \frac{t^2\sigma^2}{2}\right).

The exponent h(t):=−tε+t2σ22h(t) := -t\varepsilon + \frac{t^2\sigma^2}{2} is a convex quadratic in tt (since σ2>0\sigma^2 > 0 whenever not all ai=bia_i=b_i), minimized where h′(t)=−ε+tσ2=0h'(t) = -\varepsilon + t\sigma^2 = 0, i.e. at t∗=ε/σ2>0t^* = \varepsilon/\sigma^2 > 0 — a valid choice since t∗>0t^*>0 as required by the Chernoff bound. Substituting,

h(t∗)=−ε2σ2+12⋅ε2σ2=−ε22σ2.h(t^*) = -\frac{\varepsilon^2}{\sigma^2} + \frac{1}{2}\cdot \frac{\varepsilon^2}{\sigma^2} = -\frac{\varepsilon^2}{2\sigma^2}.

Therefore

P(Sn−μ≥ε)=P(Tn≥ε)≤exp⁡ ⁣(−ε22σ2)=exp⁡ ⁣(−ε22⋅14∑i(bi−ai)2)=exp⁡ ⁣(−2ε2∑i(bi−ai)2).\mathbb{P}(S_n - \mu \ge \varepsilon) = \mathbb{P}(T_n \ge \varepsilon) \le \exp\!\left(-\frac{\varepsilon^2}{2\sigma^2}\right) = \exp\!\left(-\frac{\varepsilon^2}{2 \cdot \frac14\sum_i(b_i-a_i)^2}\right) = \exp\!\left(-\frac{2\varepsilon^2}{\sum_i (b_i-a_i)^2}\right).

This proves the first stated inequality.

Step 4 (the two-sided and averaged versions). Applying the identical argument to −Tn=−Sn+μ=(μ−Sn)-T_n = -S_n+\mu = (\mu - S_n), whose summands −Yi-Y_i are mean-zero and supported on intervals of the same lengths bi−aib_i - a_i, gives

P(μ−Sn≥ε)≤exp⁡ ⁣(−2ε2∑i(bi−ai)2).\mathbb{P}(\mu - S_n \ge \varepsilon) \le \exp\!\left(-\frac{2\varepsilon^2}{\sum_i(b_i-a_i)^2}\right).

Since {∣Sn−μ∣≥ε}={Sn−μ≥ε}∪{μ−Sn≥ε}\{|S_n - \mu| \ge \varepsilon\} = \{S_n - \mu \ge \varepsilon\} \cup \{\mu - S_n \ge \varepsilon\}, a union of two disjoint events, subadditivity of probability gives the two-sided bound as the sum of the two one-sided bounds, i.e. twice the common bound. Finally, dividing by nn: {∣Xˉn−μ0∣≥ε}={∣Sn−μ∣≥nε}\{|\bar X_n - \mu_0| \ge \varepsilon\} = \{|S_n - \mu| \ge n\varepsilon\}, so substituting nεn\varepsilon for ε\varepsilon in the two-sided bound gives

P(∣Xˉn−μ0∣≥ε)≤2exp⁡ ⁣(−2n2ε2∑i(bi−ai)2).■\mathbb{P}(|\bar X_n - \mu_0| \ge \varepsilon) \le 2\exp\!\left(-\frac{2n^2\varepsilon^2}{\sum_i(b_i-a_i)^2}\right). \qquad \blacksquare
∎

Worked examples

Example 1 — asymmetric Bernoulli-type trials with unequal ranges. Suppose X1,…,X50X_1, \dots, X_{50} are independent, with Xi∼Bernoulli(pi)X_i \sim \mathrm{Bernoulli}(p_i) scaled to [0,ci][0, c_i] (i.e. Xi=ciX_i = c_i with probability pip_i and 00 otherwise), where the ranges alternate: ci=2c_i = 2 for ii odd (2525 of them) and ci=3c_i = 3 for ii even (2525 of them), and pip_i varies but is unspecified beyond boundedness (Hoeffding's inequality needs no knowledge of pip_i at all). We want a bound on P(S50−μ≥20)\mathbb{P}(S_{50} - \mu \ge 20) where μ=E[S50]\mu = \mathbb{E}[S_{50}]. Here ai=0a_i = 0 for all ii, so (bi−ai)2=ci2(b_i - a_i)^2 = c_i^2. Compute

∑i=150(bi−ai)2=25⋅22+25⋅32=25⋅4+25⋅9=100+225=325.\sum_{i=1}^{50} (b_i-a_i)^2 = 25 \cdot 2^2 + 25\cdot 3^2 = 25\cdot 4 + 25\cdot 9 = 100 + 225 = 325.

By Hoeffding's inequality with ε=20\varepsilon = 20:

P(S50−μ≥20)≤exp⁡ ⁣(−2(20)2325)=exp⁡ ⁣(−800325)=exp⁡(−2.4615…)≈0.0853.\mathbb{P}(S_{50}-\mu \ge 20) \le \exp\!\left(-\frac{2 (20)^2}{325}\right) = \exp\!\left(-\frac{800}{325}\right) = \exp(-2.4615\ldots) \approx 0.0853.

So regardless of the individual success probabilities pip_i (they could all be different, unknown, even adversarially chosen), the chance the weighted sum exceeds its mean by 2020 is at most about 8.5%8.5\%. Note this bound required zero distributional information beyond the ranges [0,ci][0,c_i] — a striking illustration of the theorem's distribution-free character.

Example 2 — comparing Chebyshev and Hoeffding numerically, sample mean of [−1,3][-1,3]-valued variables. Let X1,…,X100X_1,\dots,X_{100} be i.i.d. with Xi∈[−1,3]X_i \in [-1,3] almost surely, E[Xi]=1\mathbb{E}[X_i] = 1 and (say) Var(Xi)=1\mathrm{Var}(X_i) = 1 — consistent with, e.g., a scaled Beta-type distribution on [−1,3][-1,3] with these moments. We want P(∣Xˉ100−1∣≥0.3)\mathbb{P}(|\bar X_{100} - 1| \ge 0.3). Chebyshev. Since Var(Xˉ100)=Var(X1)/100=1/100=0.01\mathrm{Var}(\bar X_{100}) = \mathrm{Var}(X_1)/100 = 1/100 = 0.01, Chebyshev's inequality gives

P(∣Xˉ100−1∣≥0.3)≤0.010.32=0.010.09=0.11‾.\mathbb{P}(|\bar X_{100}-1|\ge 0.3) \le \frac{0.01}{0.3^2} = \frac{0.01}{0.09} = 0.1\overline{1}.

Hoeffding. Here bi−ai=3−(−1)=4b_i - a_i = 3-(-1) = 4 for every ii, so ∑i(bi−ai)2=100⋅16=1600\sum_i (b_i-a_i)^2 = 100\cdot 16 = 1600. With n=100n=100, ε=0.3\varepsilon = 0.3:

P(∣Xˉ100−1∣≥0.3)≤2exp⁡ ⁣(−2⋅1002⋅0.321600)=2exp⁡ ⁣(−2⋅10000⋅0.091600)=2exp⁡ ⁣(−18001600).\mathbb{P}(|\bar X_{100}-1|\ge 0.3) \le 2\exp\!\left(-\frac{2\cdot 100^2 \cdot 0.3^2}{1600}\right) = 2\exp\!\left(-\frac{2\cdot 10000\cdot 0.09}{1600}\right) = 2\exp\!\left(-\frac{1800}{1600}\right).

Compute the exponent: 1800/1600=1.1251800/1600 = 1.125, so the bound is 2e−1.125≈2×0.3247≈0.64942 e^{-1.125} \approx 2 \times 0.3247 \approx 0.6494. Here Hoeffding's bound (≈0.649\approx 0.649) is worse than Chebyshev's (≈0.111\approx 0.111) — a deliberately chosen regime to show Hoeffding is not universally sharper; it wins decisively as nn grows (its bound decays like e−cne^{-cn} versus Chebyshev's 1/n1/n), but for moderate nn with a small true variance relative to the range, the variance-based bound can be tighter. This is an important scope caveat: Hoeffding uses only the range [ai,bi][a_i,b_i], discarding variance information entirely, so when the true variance is much smaller than the crude proxy (b−a)2/4(b-a)^2/4 implies, Chebyshev can win at finite nn.

CounterexampleWhy boundedness cannot be dropped

Hoeffding's inequality requires each XiX_i to be supported on a bounded interval [ai,bi][a_i,b_i]. Drop this hypothesis and the exponential decay can fail entirely — even for i.i.d. mean-zero variables with finite variance. Let X1,…,XnX_1,\dots,X_n be i.i.d. with the (heavy-tailed but finite-variance) density

f(x)=2∣x∣3for ∣x∣≥1,f(x)=0 for ∣x∣<1,f(x) = \frac{2}{|x|^3} \quad \text{for } |x| \ge 1, \qquad f(x) = 0 \text{ for } |x|<1,

symmetrized so E[Xi]=0\mathbb{E}[X_i]=0 (the density above, restricted and signed symmetrically about 00, gives E[Xi2]=∫1∞x2⋅2x3 dx\mathbb{E}[X_i^2] = \int_1^\infty x^2 \cdot \frac{2}{x^3}\,dx pattern — concretely, take XiX_i with P(Xi≥x)=P(Xi≤−x)=12x2\mathbb{P}(X_i \ge x) = \mathbb{P}(X_i \le -x) = \frac{1}{2x^2} for x≥1x\ge1, a symmetric Pareto-type law). This law has E[Xi]=0\mathbb{E}[X_i]=0 and finite variance σ2=E[Xi2]<∞\sigma^2 = \mathbb{E}[X_i^2] < \infty (a short computation with the Pareto tail exponent 22 shows the second moment converges, e.g. Var(Xi)=2\mathrm{Var}(X_i)=2), but its moment generating function is infinite for every t≠0t \ne 0:

MXi(t)=E[etXi]=∞for all t≠0,M_{X_i}(t) = \mathbb{E}[e^{tX_i}] = \infty \quad \text{for all } t \ne 0,

because etx⋅1x3e^{tx}\cdot \frac{1}{x^3} is not integrable at ∞\infty for any t>0t>0 (the exponential eventually dominates any polynomial decay). Consequently the entire Chernoff machine breaks down at its first step: the bound P(X≥a)≤inf⁡t>0e−taMX(t)\mathbb{P}(X\ge a)\le \inf_{t>0}e^{-ta}M_X(t) is vacuous, since MX(t)=∞M_X(t)=\infty for every t>0t>0, giving the useless bound P(X≥a)≤∞\mathbb{P}(X\ge a)\le \infty. No exponential tail bound of Hoeffding's type can hold for Sn=∑XiS_n = \sum X_i: it is a classical fact for such regularly-varying tails that P(Sn≥εn)\mathbb{P}(S_n \ge \varepsilon n) decays only polynomially in nn (governed by the single-summand tail, via subexponential large-deviation theory), not exponentially. Chebyshev's inequality still applies here (it only needs finite variance) and gives the correct polynomial-order bound P(∣Xˉn∣≥ε)≤σ2/(nε2)\mathbb{P}(|\bar X_n|\ge\varepsilon)\le \sigma^2/(n\varepsilon^2) — but Hoeffding's exponential bound is simply unavailable. This shows boundedness (or at least an exponential-moment / sub-Gaussian condition) is not a technical nicety but load-bearing: without it, the qualitative conclusion (exponential decay) is false, not merely unproved.

Scope, edge cases & common traps

SituationWhat appliesWhat can go wrong
XiX_i bounded, independent, ranges knownHoeffding's inequality, exact form aboveNone — hypotheses fully met
XiX_i independent, unbounded but sub-Gaussian (e.g. Gaussian)A sub-Gaussian version with the same proof shape works, using the variance proxy directlyMust re-derive/quote the sub-Gaussian MGF bound; plain Hoeffding's Lemma no longer applies
XiX_i dependent (e.g. Markov chain, martingale differences)Needs Azuma–Hoeffding for martingale differences, not this i.i.d./independent-sum theoremApplying the stated theorem directly is invalid — independence is used essentially in Step 1 (MGF multiplicativity)
XiX_i unbounded, only finite variance (heavy tails)Chebyshev still valid; Hoeffding's Lemma inapplicableCommon error: quoting Hoeffding "because the variance is finite" — variance finiteness does not imply boundedness or sub-Gaussianity
Small nn, small true variance vs. rangeBoth Chebyshev and Hoeffding valid, compare numericallyAssuming Hoeffding is always tighter than Chebyshev — false, as Example 2 shows

The mathematician behind it

Origins · 1 minWassily Hoeffding and how this was discovered
WH
Wassily Hoeffding
1914–1991 · Probability theory and non-parametric statistics, Institute of Statistics, University of North Carolina

Wassily Hoeffding was born in Finland to a family that soon relocated, and he was educated in Germany, earning his doctorate in Berlin in 1940 under difficult wartime circumstances. He emigrated to the United States in the 1940s and became one of the founding figures of modern mathematical statistics at the University of North Carolina, where he worked alongside a generation building rigorous non-parametric and asymptotic theory. Hoeffding is remembered for U-statistics (a broad generalization of the sample mean and variance with elegant asymptotic theory) and for the 1963 paper "Probability Inequalities for Sums of Bounded Random Variables," which introduced the inequality bearing his name and remains, six decades later, one of the most cited papers in all of statistics and computer science.

History
- 1912–1914: Wassily Hoeffding born; early career shaped by mathematical training in Germany.
- 1940: Hoeffding completes his doctorate in Berlin during a period of severe academic disruption.
- 1946: Herman Chernoff, working independently on large-deviation-type bounds, develops the exponential-tilting technique later named the Chernoff bound in sequential analysis and hypothesis testing contexts.
- 1963: Hoeffding publishes "Probability Inequalities for Sums of Bounded Random Variables" in the Journal of the American Statistical Association, proving the lemma and inequality presented here.
- 1980s–present: The Chernoff–Hoeffding framework becomes foundational in computational learning theory (PAC learning), randomized algorithms, and high-dimensional statistics.
Is Hoeffding's inequality only for i.i.d. random variables?

No. The version proved here requires only independence, not identical distribution: each XiX_i may have its own distribution, as long as it is confined to its own interval [ai,bi][a_i,b_i]. This is deliberately more general than the i.i.d. case, and is essential in applications like weighted sums, unequal sample sizes, or heterogeneous randomized algorithms where different trials have different (possibly unknown) success probabilities and ranges, as in Worked Example 1.

How does Hoeffding's inequality compare to the Central Limit Theorem?

The Central Limit Theorem gives an asymptotic approximation: as n→∞n\to\infty, n(Xˉn−μ)\sqrt n(\bar X_n - \mu) converges in distribution to a Gaussian, but says nothing precise about any fixed, finite nn, and gives no explicit tail bound. Hoeffding's inequality gives an explicit, valid-for-every-nn, non-asymptotic exponential bound on the tail probability, at the cost of using only boundedness rather than the exact limiting shape. The two views are complementary: CLT describes the bulk of the distribution's shape in the limit; Hoeffding controls the tails uniformly at every finite sample size.

Why does the bound involve (bi−ai)2(b_i - a_i)^2 rather than the variance Var(Xi)\mathrm{Var}(X_i)?

Hoeffding's Lemma bounds the MGF using only the range of XiX_i, producing the variance proxy (bi−ai)2/4(b_i-a_i)^2/4, which is always an upper bound on the true variance (this can be shown via the Bhatia–Davis inequality: for X∈[a,b]X\in[a,b], Var(X)≤(b−a)2/4\mathrm{Var}(X)\le (b-a)^2/4, with equality only for a two-point {a,b}\{a,b\}-valued variable). Using range instead of variance sacrifices sharpness when the true variance is much smaller than (b−a)2/4(b-a)^2/4, but gains distribution-freeness: no knowledge of the exact variance, shape, or higher moments of XiX_i is required, only its support.

Can Hoeffding's inequality be applied to sampling without replacement?

Not directly — the proof relies essentially on independence for the MGF factorization step. Sampling without replacement from a finite population induces negative dependence among draws. However, a classical extension (the Hoeffding–Serfling inequality) proves an analogous exponential bound for sampling without replacement, exploiting the negative correlation structure; this is a genuinely different theorem requiring a separate proof, not a corollary of the independent-sum version stated here.

What happens to the bound as n→∞n \to \infty for the sample mean version?

For the averaged form, P(∣Xˉn−μ0∣≥ε)≤2exp⁡(−2nε2/c2)\mathbb{P}(|\bar X_n - \mu_0|\ge \varepsilon) \le 2\exp(-2n\varepsilon^2/c^2) when all ranges are equal to a common length cc (since then ∑(bi−ai)2=nc2\sum(b_i-a_i)^2 = nc^2, and the n2n^2 in the numerator cancels one power of nn in the denominator). This bound tends to 00 exponentially fast in nn for any fixed ε>0\varepsilon>0, which is a quantitative, non-asymptotic form of the weak law of large numbers with an explicit convergence rate, strictly stronger than the qualitative statement the law itself provides.

Is the constant in Hoeffding's inequality tight?

The variance proxy (b−a)2/4(b-a)^2/4 in Hoeffding's Lemma is tight in the sense that it is attained (in the limit) by a symmetric two-point Bernoulli-type variable taking values aa and bb with probabilities approaching 1/21/2 each. For general bounded distributions the bound can be loose (as in Worked Example 2, where the true variance is far below the proxy), so tighter but more complex alternatives (Bennett's or Bernstein's inequalities, which incorporate the true variance) are often preferred when variance information is available.

Before this