Chebyshev’s Inequality and Finite-Variance Tails

Finite Variance Gives a Deviation Guarantee

Concentration bounds turn assumptions about a distribution into statements about how far a random quantity is likely to be from its mean. Hoeffding’s inequality gives an exponential guarantee when observations are bounded. A useful contrast is the guarantee available under only a finite-variance assumption: Chebyshev’s inequality. It applies to distributions with unbounded support, but its confidence radius grows more quickly as the requested failure probability decreases.

The distinction is important in learning problems. A loss or observation need not be bounded for its mean to exist and its variance to be finite. In that setting, a finite-variance guarantee remains available, but it should not be mistaken for an exponential tail bound.

Definition: A random variable \(X\) has finite variance if \(E[X]=\mu\) exists and \(E[(X-\mu)^2]=\sigma^2<\infty\). The quantity \(\sigma^2\) measures the expected squared deviation from the mean.

Chebyshev’s Inequality

Chebyshev’s inequality bounds the probability that a random variable deviates from its mean by at least a specified positive amount. Its only distributional requirement is finite variance.

Theorem (Chebyshev’s inequality): If \(X\) has mean \(\mu\) and finite variance \(\sigma^2\), then, for every \(t>0\),

P(|X-\mu|\ge t)\le \frac{\sigma^2}{t^2}.

To prove the result, note that on the event \(|X-\mu|\ge t\), the squared deviation is at least \(t^2\). Equivalently, for every outcome,

\mathbf{1}\{|X-\mu|\ge t\}\le \frac{(X-\mu)^2}{t^2}.

Taking expectations preserves the inequality. The expectation of the indicator is the probability of its event, while \(E[(X-\mu)^2]=\sigma^2\). Therefore,

P(|X-\mu|\ge t) =E[\mathbf{1}\{|X-\mu|\ge t\}] \le \frac{E[(X-\mu)^2]}{t^2} =\frac{\sigma^2}{t^2}.

\(\square\)

The proof also shows the basic mechanism: the squared deviation is nonnegative and has a known expectation. A large deviation requires a large squared deviation on that event, so the event cannot have probability greater than the available second-moment budget divided by \(t^2\).

Worked Example: A Chebyshev Bound for a Normal Observation

Suppose \(X\sim N(10,4)\). Find a Chebyshev upper bound for \(P(|X-10|\ge 3)\).

The mean is \(\mu=10\), and because the second parameter in \(N(\mu,\sigma^2)\) is the variance, \(\sigma^2=4\). Substituting \(t=3\) gives

P(|X-10|\ge 3)\le \frac{4}{3^2}=\frac{4}{9}\approx 0.444.

This is a valid bound, though not a sharp description of the normal tail. Chebyshev uses only the variance; it does not use the more detailed shape of the normal distribution.

Applying the Bound to a Sample Mean

Let \(X_1,\ldots,X_n\) be independent and identically distributed random variables with mean \(\mu\) and finite variance \(\sigma^2\). Their sample mean is \(\bar X=n^{-1}\sum_{i=1}^n X_i\). Independence makes the variance of the sum equal to the sum of the variances, so

E[\bar X]=\mu, \qquad \operatorname{Var}(\bar X) =\frac{1}{n^2}\sum_{i=1}^n\operatorname{Var}(X_i) =\frac{\sigma^2}{n}.

Applying Chebyshev’s inequality to \(\bar X\) gives a deviation bound that improves with sample size.

Theorem (Chebyshev bound for a sample mean): If \(X_1,\ldots,X_n\) are independent and identically distributed with finite mean \(\mu\) and variance \(\sigma^2\), then, for every \(\varepsilon>0\),

P(|\bar X-\mu|\ge \varepsilon) \le \frac{\sigma^2}{n\varepsilon^2}.

The result follows by substituting \(\operatorname{Var}(\bar X)=\sigma^2/n\) into Chebyshev’s inequality:

P(|\bar X-\mu|\ge \varepsilon) \le \frac{\operatorname{Var}(\bar X)}{\varepsilon^2} =\frac{\sigma^2}{n\varepsilon^2}.

For a requested failure probability \(0<\delta<1\), choose \(\varepsilon=\sigma/\sqrt{n\delta}\). Then

P\left(|\bar X-\mu|\ge \frac{\sigma}{\sqrt{n\delta}}\right)\le\delta, \qquad P\left(|\bar X-\mu|< \frac{\sigma}{\sqrt{n\delta}}\right)\ge 1-\delta.

Thus a finite-variance confidence radius is \(\sigma/\sqrt{n\delta}\). This is a probability guarantee, not a claim that every realized sample mean falls within that distance. It is also only useful as a numerical radius when the variance is known or a valid upper bound for it is available.

Worked Example: A Confidence Radius with Finite Variance

Suppose \(X_1,\ldots,X_{25}\) are independent and identically distributed with mean \(\mu\) and variance \(4\). Find the Chebyshev radius for failure probability \(\delta=0.05\).

Here \(\sigma=2\), \(n=25\), and \(\sqrt{n\delta}=\sqrt{25(0.05)}=\sqrt{1.25}\). Therefore the radius is

\frac{\sigma}{\sqrt{n\delta}} =\frac{2}{\sqrt{1.25}} \approx 1.789.

The guarantee is

P(|\bar X-\mu|<1.789)\ge 0.95.

This conclusion requires independence, a common mean and variance, and the stated variance value. It does not require the observations to be bounded or normally distributed.

Identical distributions are not essential to the variance calculation. If the observations are independent, have means \(\mu_i\), and have finite variances \(\sigma_i^2\), then the average has mean \(\bar\mu=n^{-1}\sum_i\mu_i\) and variance \(n^{-2}\sum_i\sigma_i^2\). Chebyshev therefore gives

P\left(\left|\frac{1}{n}\sum_{i=1}^n X_i-\bar\mu\right|\ge\varepsilon\right) \le \frac{\sum_{i=1}^n\sigma_i^2}{n^2\varepsilon^2}.

The proof is the same substitution: independence gives the variance of the average, and Chebyshev applies to that average. Without independence, covariance terms may contribute to its variance, so the displayed formula does not follow as written.

Finite Variance Does Not Mean Exponential Tails

Chebyshev’s probability bound decreases as \(t^{-2}\). That polynomial dependence is a consequence of using only a second moment; finite variance does not rule out substantial probability at very large values. The next example makes this distinction explicit.

Worked Example: A Finite-Variance Distribution with Polynomial Tails

Define a discrete random variable by assigning probability \(c/k^4\) to each of \(k\) and \(-k\), for every positive integer \(k\). The normalizing constant satisfies

2c\sum_{k=1}^{\infty}\frac{1}{k^4}=1, \qquad c=\frac{1}{2\zeta(4)}.

Symmetry gives \(E[X]=0\). Its variance is finite and equals

\operatorname{Var}(X)=E[X^2] =2c\sum_{k=1}^{\infty}\frac{k^2}{k^4} =2c\zeta(2) =\frac{\zeta(2)}{\zeta(4)} =\frac{15}{\pi^2}.

But for any positive integer \(m\), the positive tail satisfies

P(X\ge m) =c\sum_{k=m}^{\infty}\frac{1}{k^4} \ge c\int_m^\infty x^{-4}\,dx =\frac{c}{3m^3}.

The integral inequality holds because \(x^{-4}\) is decreasing, so the sum over integer \(k\ge m\) is at least the integral from \(m\) to infinity. This distribution has finite variance, yet its tail has a polynomial lower bound. In particular, finite variance alone cannot justify a universal exponential tail guarantee for an individual observation.

Comparing Polynomial and Exponential Confidence Radii

For independent observations bounded in a known interval \([a,b]\), Hoeffding’s inequality gives

P(|\bar X-E[\bar X]|\ge\varepsilon) \le 2\exp\left(-\frac{2n\varepsilon^2}{(b-a)^2}\right).

Solving this inequality for a radius with failure probability at most \(\delta\) gives \((b-a)\sqrt{\log(2/\delta)/(2n)}\). By contrast, Chebyshev gives \(\sigma/\sqrt{n\delta}\) under finite variance. Both radii scale as \(n^{-1/2}\) when \(\delta\) is fixed. Their dependence on \(\delta\) differs: Chebyshev grows as \(\delta^{-1/2}\), while the Hoeffding radius grows as \(\sqrt{\log(2/\delta)}\). The exponential guarantee needs the stronger boundedness assumption.

Worked Example: Comparing Two Valid Radii

Let \(X_1,\ldots,X_{100}\) be independent Bernoulli observations with success probability \(1/2\). Each observation lies in \([0,1]\), has mean \(1/2\), and has variance \(1/4\). For \(\delta=0.05\), Chebyshev’s radius is

\frac{\sigma}{\sqrt{n\delta}} =\sqrt{\frac{1/4}{100(0.05)}} =\sqrt{0.05} \approx 0.224.

Hoeffding’s radius, using \(b-a=1\), is

\sqrt{\frac{\log(2/\delta)}{2n}} =\sqrt{\frac{\log(40)}{200}} \approx \sqrt{0.01844} \approx 0.136.

Both bounds guarantee coverage of at least \(0.95\), but the Hoeffding radius is smaller here. This comparison illustrates the cost of relying only on variance; it does not make the bounds interchangeable. Hoeffding’s inequality uses the known bounded range, while the Chebyshev calculation needs only the variance.

Common Pitfall

A common mistake is to treat finite variance as if it implied an exponential tail. The reasoning might be: “The average has variance \(\sigma^2/n\), so its deviations must be exponentially unlikely.” The variance calculation is correct, but that conclusion does not follow from it. Applying Chebyshev gives a probability bound proportional to \(1/(n\varepsilon^2)\), not an exponential in \(n\varepsilon^2\). An exponential bound requires additional assumptions, such as the boundedness used by Hoeffding’s inequality. Check the assumptions before choosing the rate.

Key takeaway: Finite variance gives a valid sample-mean confidence radius of \(\sigma/\sqrt{n\delta}\). It requires neither bounded observations nor a particular distributional shape, but its polynomial dependence on the failure probability can be much less favorable than the dependence in exponential bounds.

Check Your Understanding

Try these questions before moving on.

State the only moment assumption needed for Chebyshev’s inequality and write its two-sided deviation bound.
For independent, identically distributed observations with variance \(\sigma^2\), derive the variance of their sample mean.
How does the Chebyshev confidence radius change when the failure probability is reduced from \(\delta\) to \(\delta/4\), with \(n\) and \(\sigma^2\) fixed?
Why does a finite variance not, by itself, justify applying Hoeffding’s inequality?
For independent observations with unequal variances, what expression replaces \(\sigma^2/n\) as the variance of their average?