Chebyshev's Inequality (Prob.)

P(|X - | ≥ k ) ≤ 1/k^2 — Markov's variance-flavored sibling.

The idea

Theorem (Chebyshev's inequality).

Let $X$ have mean $\mu$ and standard deviation $\sigma$. Then for every $k > 0$, $\mathbb{P}(|X - \mu| \geq k\sigma) \leq \frac{1}{k^{2}}.$

The guarantee holds for every distribution at once. Whatever $X$ is — the figure's lopsided density is a reminder that nothing is assumed about shape or symmetry — the probability of landing $k$ or more standard deviations from the mean is at most $1/k^{2}$, and the cap tightens quadratically as $k$ grows. The only requirement is that the mean and variance exist.

The deviation is measured in units of $\sigma$, so the statement does not depend on the units of $X$: rescaling $X$ rescales $\sigma$ with it, and $k$ is unchanged.

Universality costs sharpness. For any particular distribution the true tail probability usually falls far below $1/k^{2}$, because the bound must cover the worst distribution with the given mean and variance. Its value is that it needs so little: knowing only a mean and a variance, it is often the only tail bound available.

Ways to work on it

• Walkthrough. Bound the probability that a random variable strays far from its mean.
• Proof. Derive Chebyshev by applying Markov to (X - )^2.
• Practice. Bound a tail probability in two steps from a given mean and standard deviation.
• Hardest. Bound a tail probability from a mean and a variance in a single step.

Not sure where to start? Take the ten-question placement test.