Chebyshev's inequality

Imagine two factories making bolts to the same average length. One is sloppy with wildly varying lengths; the other is consistent. If you grab a bolt at random, the consistent factory's bolt is far more likely to be near the target. Chebyshev's inequality turns this intuition into a guarantee: the more tightly clustered a quantity is around its mean — the smaller its variance — the less likely it is to stray far.

Precisely: for any random variable X with mean mu and variance sigma^2, and any t > 0, Pr[ |X - mu| >= t ] <= sigma^2 / t^2. Setting t = k sigma gives the memorable form Pr[ |X - mu| >= k sigma ] <= 1/k^2 — being more than k standard deviations from the mean happens at most a 1/k^2 fraction of the time, for any distribution at all. The proof is just Markov in disguise: apply Markov's inequality to the nonnegative variable (X - mu)^2, whose mean is exactly sigma^2, with threshold t^2; Pr[(X - mu)^2 >= t^2] <= sigma^2 / t^2, and (X - mu)^2 >= t^2 is the same event as |X - mu| >= t. Because it uses the variance, Chebyshev shrinks like 1/k^2, far faster than Markov's 1/k.

Chebyshev is the natural next tool when you can compute or bound a variance — for instance when your quantity is a sum of pairwise-independent (not necessarily fully independent) indicators, where variances add nicely. It powers the analysis of universal hashing's collision counts and many sampling estimates. The honest caveat: it is symmetric and distribution-free, so it stays conservative; when your variable is a sum of many independent pieces, Chernoff exploits that structure to give bounds that shrink exponentially in k, dramatically beating Chebyshev's polynomial 1/k^2.