Concentration Inequalities for Algorithm Design

Core Idea

Concentration inequalities — Chernoff bounds, Hoeffding's inequality, Azuma-Hoeffding martingale inequality, and the Lovasz Local Lemma — form the essential probability toolkit for designing and analyzing randomized algorithms. Chernoff bounds show that sums of independent Bernoulli random variables are exponentially concentrated around their mean: Pr[X > (1+delta)*mu] <= (e^delta / (1+delta)^1+delta)^mu. The Azuma-Hoeffding inequality extends concentration to martingale sequences, enabling analysis when variables are exposed one at a time (as in randomized rounding or random graph processes). The Lovasz Local Lemma provides existence guarantees when bad events are mostly independent: if each bad event has probability at most p and depends on at most d others, and ep(d+1) <= 1, then with positive probability none of the bad events occur. These tools are used throughout streaming algorithms, randomized data structures, and derandomization.

Explainer

Concentration inequalities are the quantitative backbone of randomized algorithm analysis. While linearity of expectation tells you the average behavior, concentration inequalities tell you how tightly the actual behavior clusters around that average — and in algorithm design, the difference between "good in expectation" and "good with high probability" is the difference between a usable algorithm and a theoretical curiosity.

Chernoff bounds are the most frequently used tool. For a sum X of n independent random variables in [0,1] with mean mu, the multiplicative Chernoff bound states P(X >= (1+delta)*mu) <= (e^delta / (1+delta)^1+delta)^mu, which simplifies to P(X >= (1+delta)*mu) <= exp(-mu*delta²/3) for delta in (0,1). The key feature is exponential decay in mu: the probability of deviating by a constant fraction drops exponentially with the expected value. This makes Chernoff bounds indispensable for randomized rounding (where you need the rounded objective to be close to the LP optimum), load balancing (where n balls thrown into n bins gives maximum load O(log n / log log n) via Chernoff + union bound), and hashing (where Chernoff bounds guarantee that hash table load stays balanced with high probability).

The Azuma-Hoeffding inequality generalizes concentration to martingale sequences, handling situations where the random variables are not independent. If Z_0, Z_1, ..., Z_n is a martingale with bounded increments |Z_i - Z_{i-1}| <= c_i, then P(|Z_n - Z_0| >= t) <= 2*exp(-t² / (2*sum c_i²)). The Doob martingale construction connects this to functions of independent random variables: for any f(X_1,...,X_n) satisfying the bounded differences condition (changing one input changes f by at most c_i), the Doob martingale Z_i = E[f | X_1,...,X_i] has bounded increments, and Azuma-Hoeffding gives P(|f - E[f]| >= t) <= 2*exp(-t² / (2*sum c_i²)). This is McDiarmid's inequality, and it applies to functions far more general than sums — the chromatic number of a random graph, the length of the longest common subsequence, or any function where each input has bounded influence.

The Lovasz Local Lemma (LLL) operates in a fundamentally different regime. Instead of bounding how far a random variable deviates from its mean, the LLL proves that a "good" outcome exists even when many bad events could occur — as long as the bad events are mostly independent. The symmetric form states: if each of n bad events has probability at most p and is independent of all but at most d other events, and ep(d+1) <= 1, then with positive probability none of the bad events occur. The LLL is the tool of choice for satisfiability of sparse formulas, hypergraph coloring, and Latin transversals. Moser and Tardos's 2010 algorithmic version made the LLL constructive: repeatedly resample the variables involved in any bad event that occurs, and the process terminates in expected polynomial time. This transformed the LLL from a pure existence tool into a practical algorithm design technique, with applications to job scheduling, packet routing, and defective graph coloring.

Together, these four tools — Chernoff, Hoeffding, Azuma-Hoeffding, and the LLL — cover the major regimes of probabilistic analysis in algorithm design: independent sums (Chernoff/Hoeffding), sequential processes with dependencies (Azuma), and sparse dependency structures (LLL). Mastering when to apply each one, and understanding their limitations (Chernoff requires independence; Azuma requires bounded increments; the LLL requires sparse dependencies), is essential for both designing new randomized algorithms and proving that existing ones work.