the Chernoff bound
/ CHER-noff /
If you flip a fair coin ten times, getting nine heads is no shock. But flip it ten thousand times and getting 60 percent heads would be astonishing — the more independent flips you average, the more stubbornly the average glues itself to one-half. The Chernoff bound makes this 'strength in numbers' precise: a sum of many independent random pieces is exponentially unlikely to wander far from its expected value.
Precisely: let X = X_1 + ... + X_n be a sum of independent random variables each in [0,1] (often independent 0/1 indicators), with mean mu = E[X]. Then for any deviation fraction delta > 0, Pr[X >= (1 + delta) mu] and Pr[X <= (1 - delta) mu] are each at most an exponentially small quantity, roughly exp(-mu delta^2 / 3) for moderate delta. The crucial word is exponential: the failure probability shrinks like e to a negative power of mu, not like a polynomial. The proof idea is slick: apply Markov's inequality not to X but to e^(sX) for a cleverly chosen s > 0; because the X_i are independent, the expectation of the product e^(sX) factors into a product of small per-variable terms, and optimizing s yields the exponential bound. Independence is what makes that factorization legal, and it is the whole engine.
Chernoff is the heavy artillery of randomized analysis. It explains why a randomized load balancer keeps every bin near its average, why repeating a Monte Carlo test k times drives error down exponentially, why random sampling estimates concentrate, and why randomized rounding in approximation algorithms works. It matters because it converts 'expected value' into 'almost certainly close to the expected value,' which is what you need for high-probability guarantees. The honest caveat: it demands independence (or near-independence). For dependent variables you must fall back to Chebyshev or to specialized martingale bounds (Azuma), which are weaker; and the constants in the exponent vary by which form you use, so cite the version you mean.
Throw n balls into n bins uniformly at random. The expected load of any one bin is 1, and Chernoff shows the chance that a fixed bin gets more than about 3 log n / log log n balls is tiny; a union bound over all n bins then proves that, with high probability, the busiest bin holds only O(log n / log log n) balls.
Sums of independent variables concentrate exponentially tightly around their mean.
Chernoff's exponential strength comes entirely from independence; drop that and the bound is invalid. It is the reason 'expected O(...)' can be upgraded to 'O(...) with high probability', but only for sums of (near-)independent pieces.