Why the average is not enough
The previous guide gave us a superpower: linearity of expectation lets us compute the expected value of almost anything by adding up tiny indicator variables, without untangling how they depend on one another. But an expectation is a single number — the long-run average over infinitely many runs. It does not, by itself, tell you whether a single run will be close to that average or wildly off. A randomized algorithm whose expected running time is O(n log n) could, for all expectation alone knows, take a million times longer on the run you actually care about.
Here is a homely picture. Two villages each have an average income of one coin per person. In the first, everyone earns exactly one coin. In the second, one person hoards a billion coins and everyone else has nothing. Same average, utterly different lives. Tail bounds are the tools that distinguish these two worlds: they bound the probability that a random quantity lands far out in the tail of its distribution, away from its mean. For a randomized algorithm, the tail is exactly where disaster lives — the rare runs that are catastrophically slow, or the rare answers that are wrong.
Markov: the bluntest hammer
The first and weakest tool is the Markov inequality. It applies to any random variable X that is never negative, and it asks almost nothing of you: you only need to know the expectation E[X]. The claim is that X cannot be large too often, simply because if it were, the average would be dragged up past E[X]. Formally, for any threshold a > 0, the probability that X is at least a is at most E[X] divided by a. In symbols: Pr[X >= a] <= E[X] / a.
Why is it true? Think of E[X] as a weighted average of X's values. Every outcome where X >= a contributes at least a, multiplied by its probability, to that average. So the average is at least a times Pr[X >= a]. Since the average equals E[X], we get E[X] >= a * Pr[X >= a], and dividing by a gives the inequality. The non-negativity matters: if X could be very negative on other outcomes, those could cancel the large values and the argument would collapse. That single one-line proof is the entire content of Markov.
Markov is blunt because it only uses the mean. A concrete use: suppose a Las Vegas algorithm has expected running time E[T] = 5n. Markov says the probability it runs for at least 50n steps is at most 5n / 50n = 1/10. So at least 90% of the time it finishes within 10 times its average — useful, but weak. We have not used any information about the spread of T, only its center, and that is exactly why the guarantee is so loose. To do better, we need to feed the next tool a second number: the variance.
Chebyshev: paying attention to the spread
The Chebyshev inequality is Markov applied with a clever twist. We want to bound how far X strays from its mean mu = E[X]. The trick: apply Markov not to X but to the squared deviation (X - mu)^2, which is always non-negative — perfect for Markov. The expectation of that squared deviation is, by definition, the variance Var[X]. Working through Markov on (X - mu)^2 with threshold k^2 gives the clean statement: the probability that X is at least k standard deviations away from its mean is at most 1/k^2. In symbols, with sigma the standard deviation, Pr[ |X - mu| >= k*sigma ] <= 1/k^2.
Notice the upgrade. Markov's bound shrinks like 1/a — slowly. Chebyshev's shrinks like 1/k^2 — quadratically. Being 10 standard deviations out has probability at most 1/100, being 100 out at most 1/10000. The price for this sharper bound is that you must know (or bound) the variance, which is often harder to compute than the mean. But linearity of expectation has a cousin here: when your quantity is a sum of independent indicator variables, the variances add too, so the variance is often still tractable.
Chernoff: when many coins flip independently
The Chernoff bound is the heavy artillery, and it applies in a very common special case: when X is a sum of independent 0/1 variables — exactly the indicator sums that linearity of expectation loves. Think of flipping n biased coins and letting X count the heads, with mean mu = E[X]. Chernoff says the probability that X overshoots its mean by even a modest fraction decays not polynomially but exponentially in mu. A representative form: Pr[ X >= (1 + delta) * mu ] <= exp( - delta^2 * mu / 3 ) for 0 < delta <= 1, with a matching bound for falling far below the mean.
Bounding Pr[X >= a] for X = sum of independent 0/1 vars, mean mu: Markov : Pr[X >= a] <= mu / a (shrinks like 1/a) Chebyshev : Pr[|X - mu| >= k*sigma] <= 1 / k^2 (shrinks like 1/k^2) Chernoff : Pr[X >= (1+delta)*mu] <= exp(-delta^2*mu/3) (shrinks like e^-mu) More assumptions ==> much sharper bound.
Feel the difference numerically. Flip n = 100 fair coins, so mu = 50. What is the chance of getting at least 75 heads (delta = 1/2)? Chebyshev, using variance 25 and so sigma = 5, places 75 at 5 standard deviations out, giving a bound of 1/25 = 0.04 — already small. Chernoff gives roughly exp(-(1/4)(50)/3) = exp(-4.17), about 0.015, and tightens furious-fast as n grows: at n = 10000 the same relative overshoot becomes astronomically unlikely. This exponential decay is precisely what lets us say a Monte Carlo algorithm is right not just on average but with overwhelming probability.
Be honest about the price of this power: Chernoff comes with a real assumption that Markov and Chebyshev did not need. The 0/1 variables must be independent (or at least negatively associated). If your indicators are tangled — say, they describe whether overloaded bins exist and one bin being full makes another more likely to be empty — the basic Chernoff bound may simply not apply. Independence is the price of the exponential. This is the honest counterpart to linearity of expectation, which needed no independence at all; here, the stronger conclusion demands the stronger hypothesis.
Turning a tail bound into a guarantee
Tail bounds are not just decoration; they are how an expected-time result becomes a high-probability result. Take randomized quicksort, whose expected running time we know is O(n log n). Its worst case is still Theta(n^2) — that never goes away, since an unlucky stream of pivot choices can always happen. But tail bounds let us prove that the unlucky streams are vanishingly rare: one can show that randomized quicksort runs in O(n log n) time not merely on average but with probability at least 1 - 1/n, so the chance of even mildly bad behaviour shrinks as the input grows.
- Express the quantity you fear (running time, number of errors, max load) as a sum of indicator random variables, the way the previous guide taught.
- Compute its expectation by linearity of expectation — this gives the center you will measure deviation from.
- Pick the weakest tool that still suffices: Markov if you only know the mean, Chebyshev if you can bound the variance, Chernoff if the terms are independent and you need an exponentially small tail.
- Read off the failure probability, and if it is not yet tiny, repeat the algorithm independently and combine runs to drive it toward zero.
That last step is the engine of randomized algorithms. A Monte Carlo algorithm that is correct with probability, say, 2/3 sounds shaky — but run it k independent times and take a majority vote, and a Chernoff bound on the number of correct runs shows the majority is wrong with probability exponentially small in k. A handful of repetitions can push a one-in-three error down past one-in-a-billion. This is probability amplification, and it is only rigorous because a tail bound certifies that the lucky majority overwhelmingly happens.
Keep one honest perspective as you climb to the next guides. A tail bound never abolishes the bad case — randomized quicksort's Theta(n^2) worst case is still genuinely reachable, just astronomically improbable. What the bound buys is a precise, provable promise about how improbable. That is the whole bargain of randomization: you trade a hard worst-case guarantee for a probabilistic one that, thanks to Markov, Chebyshev, and Chernoff, can be made as close to certainty as you are willing to pay repetitions for.