Chebyshev's Inequality

Motivation

Markov’s inequality uses only the mean. Chebyshev’s inequality uses both mean and variance to get stronger bounds on deviations.

Statement

For any random variable $X$ with finite mean $\mu$ and finite variance $\sigma^2$:

$P(|X - \mu| \geq k\sigma) \leq \frac{1}{k^2}$

for any $k > 0$.

Alternative Form

$P(|X - \mu| \geq a) \leq \frac{\sigma^2}{a^2}$

Proof

Apply Markov’s inequality to $(X - \mu)^2$, which is non-negative with mean $\sigma^2$:

$P(|X - \mu| \geq a) = P((X - \mu)^2 \geq a^2) \leq \frac{E[(X - \mu)^2]}{a^2} = \frac{\sigma^2}{a^2}$

Substitute $a = k\sigma$:

$P(|X - \mu| \geq k\sigma) \leq \frac{\sigma^2}{k^2\sigma^2} = \frac{1}{k^2}$

Interpretation

| $k$ | $P(|X - \mu| \geq k\sigma)$ | |-----|----------------------------| | 1 | $\leq 1$ (useless bound) | | 2 | $\leq 0.25$ | | 3 | $\leq 0.11$ |

For ANY distribution (with finite variance), at most 25% of values lie beyond 2 standard deviations from the mean, and at most 11% beyond 3 standard deviations.

Compare to normal: For $N(\mu, \sigma^2)$, $P(|X - \mu| \geq 2\sigma) \approx 0.05$ and $P(|X - \mu| \geq 3\sigma) \approx 0.003$. Chebyshev gives worst-case bounds.

Visualisation

Example

Test scores have mean 70 and variance 100 (SD = 10). What proportion might score below 50 or above 90?

$|X - 70| \geq 20 = 2\sigma$.

$P(|X - 70| \geq 20) \leq \frac{1}{4}$

At most 25% can be more than 20 points from the mean.

For a normal distribution, this would be about 5%: Chebyshev is conservative.

Example: Sample Mean

Let $\bar{X}_n = \frac{1}{n}\sum_{i=1}^n X_i$ where $X_i$ are i.i.d. with mean $\mu$ and variance $\sigma^2$.

$E[\bar{X}_n] = \mu$ and $\text{Var}(\bar{X}_n) = \sigma^2/n$.

$P\left(|\bar{X}_n - \mu| \geq \epsilon\right) \leq \frac{\sigma^2/n}{\epsilon^2} = \frac{\sigma^2}{n\epsilon^2}$

This decays as $n \to \infty$: the sample mean concentrates around $\mu$.

One-Sided Chebyshev

For $P(X - \mu \geq a)$ (one direction only), we can use:

$P(X - \mu \geq a) \leq \frac{\sigma^2}{\sigma^2 + a^2}$

Better than two-sided Chebyshev of $\sigma^2/a^2$ when $a/\sigma < 1$.

Comparison with Markov

Inequality	Information Required	Bound
Markov	$E[X]$, $X \geq 0$	$P(X \geq a) \leq E[X]/a$
Chebyshev	$E[X]$, $\text{Var}(X)$	$P(

Chebyshev is stronger but requires variance (and is symmetric about the mean).

Application: Proving Convergence

Given $\epsilon > 0$ and $n$ samples:

$P(|\bar{X}_n - \mu| \geq \epsilon) \leq \frac{\sigma^2}{n\epsilon^2}$

For any $\epsilon > 0$, choose $N > \sigma^2/\epsilon^2 \cdot \delta$ to ensure $P(|\bar{X}_n - \mu| \geq \epsilon) < \delta$ for all $n \geq N$.

Summary

Property	Statement
Condition	Finite $\mu$ and $\sigma^2$
Inequality	$P(
Alternative	$P(
Strength	Works for any distribution
Weakness	Often conservative