Questions: Concentration Inequalities for Algorithm Design

Question 1

A randomized algorithm makes n independent coin flips, each with success probability p. You want the total number of successes X to be within a (1 +/- delta) factor of its mean mu = np. Which concentration inequality is most appropriate?

• A. Markov's inequality, which gives P(X >= a) <= mu/a
• B. Chebyshev's inequality, which gives P(|X - mu| >= k*sigma) <= 1/k^2
• C. Chernoff bound, which gives P(|X - mu| >= delta*mu) <= 2*exp(-mu*delta^2/3) for delta in (0,1)
• D. Central limit theorem, which says X is approximately Gaussian for large n

Answer: (C)

Chernoff bounds are the right tool for multiplicative deviations of sums of independent random variables. For X = sum of n independent Bernoullis with mean mu = np, the Chernoff bound gives P(X >= (1+delta)*mu) <= exp(-mu*delta^2/3) for 0 < delta < 1, and P(X <= (1-delta)*mu) <= exp(-mu*delta^2/2). These bounds are exponentially decaying in mu, far tighter than Chebyshev's 1/k^2 polynomial decay. Markov's inequality is too weak (only first-moment information). The CLT gives an asymptotic approximation, not a finite-sample bound. Chernoff bounds are the workhouse for balls-into-bins, load balancing, randomized rounding, and any setting with independent binary outcomes.

Question 2

The Azuma-Hoeffding inequality requires the random variables to be independent of each other.

• T. True
• F. False

Answer: False

This is a critical distinction. Azuma-Hoeffding applies to MARTINGALE sequences, not independent sums. A martingale (or supermartingale/submartingale) captures sequential revelation of information where the conditional expectation is controlled, but the variables need not be independent. Specifically, if Z_0, Z_1, ..., Z_n is a martingale with |Z_i - Z_{i-1}| <= c_i, then P(|Z_n - Z_0| >= t) <= 2*exp(-t^2 / (2 * sum c_i^2)). This is vital for algorithm analysis where decisions depend on previous outcomes — for example, analyzing the chromatic number of a random graph by exposing edges one at a time, or proving concentration of a function of dependent random variables via the Doob martingale construction.

Question 3

Explain the Lovász Local Lemma and give an algorithmic application where it provides a non-trivial existence guarantee.

Model answer: The Lovász Local Lemma (LLL) says: given bad events A_1, ..., A_n where each P(A_i) <= p and each event is independent of all but at most d other events, if ep(d+1) <= 1, then P(none of A_i occur) > 0. Application: k-SAT satisfiability — if every clause shares variables with at most d = 2^(k-1)/e - 1 other clauses, a satisfying assignment exists. This is because each clause is unsatisfied with probability 2^(-k), and the dependency between clauses comes only from shared variables. The LLL guarantees a satisfying assignment exists even when the naive union bound fails (n * 2^(-k) could exceed 1). Moser and Tardos (2010) gave a constructive, algorithmic version of the LLL with expected runtime polynomial in n, making it a practical algorithmic tool.

The LLL is powerful precisely when individual bad events are unlikely AND their dependencies are sparse. The union bound requires sum P(A_i) < 1, which fails when there are many events. The LLL replaces this with a local condition: each event is unlikely AND interacts with few others. The Moser-Tardos algorithm makes this constructive by repeatedly resampling the variables involved in any occurring bad event.

Question 4

A Doob martingale is constructed by defining Z_i = E[f(X_1,...,X_n) | X_1,...,X_i]. Why is this useful for proving concentration of f?

• A. It converts any function into a linear function, making the analysis trivial
• B. It creates a martingale from any function of independent random variables, allowing Azuma-Hoeffding to be applied whenever the bounded differences condition holds for f
• C. It eliminates the need for independence assumptions entirely
• D. It always provides tighter bounds than Chernoff

Answer: (B)

The Doob martingale construction is the bridge between the bounded differences condition (McDiarmid's inequality) and Azuma-Hoeffding. Given independent X_1,...,X_n and any function f, define Z_0 = E[f], Z_i = E[f | X_1,...,X_i], Z_n = f(X_1,...,X_n). This is a martingale by construction (E[Z_i | Z_{i-1}] = Z_{i-1}). If changing X_i changes f by at most c_i (bounded differences), then |Z_i - Z_{i-1}| <= c_i. Applying Azuma-Hoeffding to this martingale gives P(|f - E[f]| >= t) <= 2*exp(-t^2 / (2*sum c_i^2)), which is exactly McDiarmid's inequality. The Doob construction is the standard technique for proving concentration of complex functions of independent random variables.

Question 5

In the analysis of randomized rounding for an LP relaxation, Chernoff bounds are preferred over Chebyshev's inequality because they give exponentially decaying tails instead of polynomially decaying tails.

• T. True
• F. False

Answer: True

When rounding fractional LP variables to integers independently, the rounded solution's objective is a sum of independent random variables. Chebyshev's inequality gives P(|X - mu| >= t) <= Var(X)/t^2 — polynomial in 1/t. Chernoff bounds give P(|X - mu| >= t) <= exp(-Omega(t^2/mu)) — exponential in t. This exponential decay is essential for randomized rounding because we need the rounded solution to be simultaneously close to the LP value across many constraints. A union bound over m constraints requires failure probability < 1/m per constraint; Chernoff achieves this with O(log m) factor overhead, while Chebyshev would require O(m) overhead, destroying the approximation ratio.