Markov's inequality

Suppose you know only the average commute time in a city — say 30 minutes — and nothing else. Can a quarter of commuters take 4 hours each? No: if too many people had enormous commutes, the average would have to be larger than 30 minutes. Markov's inequality is this commonsense limit made exact: a nonnegative quantity cannot be far above its average too often, because high values pull the mean up.

Precisely: if X is a nonnegative random variable and a > 0, then Pr[X >= a] <= E[X] / a. The proof is a one-line accounting argument. Since X >= 0, the expectation E[X] is at least the contribution from outcomes where X >= a, and each such outcome contributes at least a; so E[X] >= a times Pr[X >= a], and dividing by a gives the bound. A handy rephrasing: the probability that X exceeds k times its mean is at most 1/k — so X is at least 10 times its average at most 10 percent of the time. This is exactly what lets you turn a Las Vegas algorithm into a Monte Carlo one: if expected time is mu, the chance of running past 2 mu is at most one-half, so cutting off at 2 mu fails only half the time.

Markov's inequality matters because it needs almost nothing — only nonnegativity and the mean — making it the first, easiest tail bound and a building block for stronger ones (Chebyshev applies Markov to the squared deviation; Chernoff applies it to an exponential). Its honesty is also its weakness: knowing only the average, the bound is often very loose. With more information — a known variance, or independence among parts — Chebyshev and Chernoff give far tighter, exponentially small bounds. Markov is the floor, not the ceiling.