Concentration Inequalities for Algorithm Analysis: Chernoff, Azuma, and Their Assumptions

An expected bound is a statement about an average over runs, and an algorithm that is run once does not get the average. The step from “expected O(n log n) comparisons” to “exceeds 10 n log n with probability at most 10^-6” is a concentration argument, and it depends on the dependence structure of the random variables involved. Choosing an inequality whose assumptions the variables do not satisfy produces a bound that is not conservative; it is false, and the failure is silent because the formula still evaluates to a small number.

Markov and Chebyshev as the fallback

Markov’s inequality needs only non-negativity: for X ≥ 0, Pr[X ≥ t] ≤ E[X]/t. It is always applicable and almost always weak. Setting t = k E[X] gives a bound of 1/k, so a guarantee of one failure in a thousand requires the threshold to be a thousand times the expectation. For an algorithm whose cost is Θ(n) this is useless at any realistic n.

Chebyshev adds the variance: Pr[|X - E[X]| ≥ t] ≤ Var[X]/t^2. If the standard deviation is much smaller than the mean, the bound improves to a polynomial decay. For a sum of n independent bounded variables, the standard deviation grows as √n while the mean grows as n, so a deviation of a constant fraction of the mean has probability bounded by a constant over n, which is a 1/n-type bound rather than an exponential one.

These two are the only inequalities that apply without structure. Everything sharper needs either independence, negative dependence, or a martingale property.

Chernoff for sums of independent indicators

The Chernoff bound applies to a sum X = sum X_i of independent indicators, each with its own probability p_i, with mean μ = sum p_i. The multiplicative form states that for δ > 0,

$$ \Pr[X \ge (1+\delta)\mu] \le \left(\frac{e^{\delta}}{(1+\delta)^{1+\delta}}\right)^{\mu} $$

and the simpler corollary for δ in (0,1) is Pr[X ≥ (1+δ)μ] ≤ exp(-δ^2 μ / 3). The lower tail has the symmetric form Pr[X ≤ (1-δ)μ] ≤ exp(-δ^2 μ / 2), and the constants differ between the two tails, which matters when both are needed.

The proof is the moment generating function. For any t > 0, Pr[X ≥ a] = Pr[e^{tX} ≥ e^{ta}] ≤ e^{-ta} E[e^{tX}], and independence factorizes the expectation into a product of per-variable generating functions, each bounded by exp(p_i (e^t - 1)). Optimizing over t gives the stated form. Independence enters only in the factorization, and it is the only place it enters: if the generating function of the sum is bounded by the product of the individual generating functions, the conclusion holds even without independence. That relaxation is why the bound sometimes applies to negatively correlated variables.

The typical application is a randomized algorithm with n independent trials, each succeeding with probability at least 1/2. The majority vote of 2t+1 trials fails when at most t succeed, which is a deviation of order √t below the mean, giving a failure probability of exp(-Θ(t)). Reaching a failure probability of 2^-80 this way needs on the order of a hundred trials, since the exponent carries a constant below one. That factor of a hundred is the reason repetition is affordable for algorithms with a constant success probability, and unaffordable for algorithms whose success probability is already close to 1.

Azuma for martingales and bounded differences

Most algorithm analyses do not produce sums of independent variables. The random choices interact: the pivot chosen at one level of quicksort changes which subproblems exist at the next. The right tool for that structure is a martingale with bounded differences.

A sequence X_0, X_1, ..., X_n is a martingale with respect to the random choices if E[X_{i+1} | choices so far] = X_i. The Doob martingale of a function f of the random choices is defined by exposing the choices one at a time: X_i = E[f | first i choices]. It is a martingale by construction, and X_n = f, X_0 = E[f].

Azuma’s inequality states that if |X_i - X_{i-1}| ≤ c_i for every i, then

$$ \Pr[|X_n - X_0| \ge t] \le 2\exp\left(-\frac{t^2}{2\sum_i c_i^2}\right) $$

The bounded-difference condition is the substantive requirement, and it is often easy to verify: changing one random choice changes the cost by at most some known amount. For quicksort, changing one pivot choice can change the comparison count by O(n) in the worst case, so the naive bound gives c_i = O(n) for n choices and a deviation bound of exp(-t^2 / O(n^3)), which is vacuous for deviations of order n log n. The effective method for quicksort is to expose the choices in an order where each one shifts the cost by only O(log n), or to bound the cost above by a sum of independent variables and apply Chernoff to that sum.

# Doob martingale exposure for a function f of independent choices.
# At step i, X_i is the conditional expectation of f given choices[:i].
# Azuma then bounds deviations of f from E[f] by the sum of squared
# per-step differences; each difference must be bounded by c_i.

def doob_bounds(choices, f, conditional_mean):
    total_sq = 0.0
    for i in range(len(choices)):
        lo = conditional_mean(choices[:i], value=0.0)
        hi = conditional_mean(choices[:i], value=1.0)
        total_sq += (hi - lo) ** 2
    return total_sq   # deviation t has probability <= 2*exp(-t^2/(2*total_sq))

The function above computes the variance proxy sum c_i^2 under the worst-case difference at each step. It is not an implementation of Azuma but the quantity Azuma needs, and computing it is usually the hard part of applying the inequality.

Negative dependence and sampling without replacement

Many natural sums are negatively dependent: when one bucket of a hash table receives an extra key, another bucket receives one fewer. Negative dependence is often as good as independence for Chernoff-type bounds, because the moment generating function of a negatively dependent sum is bounded by the product of the individual ones. The condition is a comparison of generating functions against independent copies, and several standard families satisfy it: occupancy counts, sampling without replacement, and statistics of random permutations.

Sampling without replacement is the canonical case. Drawing k items from n without replacement has a sum whose tail is bounded by the Chernoff bound for sampling with replacement, which is the Hoeffding-style result for hypergeometric variables. The intuition is that sampling without replacement is less variable than sampling with replacement, because the draws cannot repeat; the bound follows from a coupling in which the without-replacement draw is obtained from a with-replacement draw by rejection.

For occupancy, the number of balls in a given bin is binomial and the counts across bins are negatively associated. The maximum load over m bins with n balls is bounded by analysing one bin and applying a union bound over the bins, and the negative association is what allows the per-bin Chernoff bound to be applied without a correction for the dependence.

The union bound and its misuse

The simplest concentration tool is the union bound, and it is the one most often applied without checking that the events are being counted correctly. If there are N bad events, each with probability at most p, the probability that any occurs is at most N p. The bound is exact when the events are disjoint and weak when they overlap heavily.

The misuse is in the choice of N. For a randomized algorithm with n possible failure points, N = n is correct only if the algorithm can fail at exactly those points and the failure probability at each is p. If the algorithm runs T steps and can fail at any of them, the union bound over steps gives T p, and T may be much larger than n. When the running time is itself random, the number of steps is not a fixed quantity, and the union bound over a random number of events requires conditioning on the step count.

The correct treatment for a random number of trials is to bound the probability of failure at step i conditional on reaching step i, and to multiply by the probability of reaching it, summing over i. That is a union bound over a random set of events, and it is valid; the naive version that multiplies the maximum per-step failure probability by the expected number of steps is not.

Comparing the tools on one problem

Consider the maximum load in a hash table with n keys and n buckets and a fully random hash. The load of a fixed bucket is a sum of n independent indicators with mean 1, and the Chernoff bound gives Pr[load ≥ k] ≤ exp(-k ln k) for k above e. The union bound over n buckets gives n exp(-k ln k), which is below 1 when k is about ln n / ln ln n. That is the standard high-probability bound, and it is tight up to constants.

With a pairwise-independent hash family instead of a fully random one, the mean is the same and the variance is the same, but the Chernoff bound does not apply. The correct tool is Chebyshev, which gives a bound of order 1/k^2 on the load of one bucket, and the union bound then gives n/k^2, which is below 1 only for k around √n. The gap between ln n / ln ln n and √n is the price of weakening the independence assumption, and it is not a constant-factor price.

That comparison is the practical content of the concentration toolchain. The choice of hash family determines which inequality is available, and the inequality determines the guarantee. A table with a fully random hash gets a logarithmic maximum load; a table with a pairwise-independent family gets a square-root one. Both are correct, and neither is obtained by applying the wrong inequality to the right distribution.

The analyses in Universal Hashing and Guarantees That Hold for Every Input use the weaker end of this spectrum, and the existence proofs in The Probabilistic Method use the union bound in its pure form. The step from one to the other is precisely the step from an expectation to a guarantee about a single run.