Concentration Inequalities: from the Chernoff Method to the Stochastic TSP

There's really only one idea here, and it's worth saying up front: every concentration bound in this post is one of two moves — bound a moment generating function, or turn your quantity into a sum of martingale differences so you can bound MGFs one coordinate at a time. Everything else is bookkeeping about what structure you're allowed to assume.

0. Notation

Fixed once and used everywhere.

Throughout, $t\ge 0$ is the deviation scale and $\lambda$ is the dual variable of the Chernoff method. "Increasing" always means coordinatewise nondecreasing.

1. The dependency map

Read top-to-bottom. The post follows this order exactly.

                        Markov's inequality
                                |
                +---------------+-------------------------------+
                |                                               |
          Chebyshev                              Cramer-Chernoff method
        (2nd moment only)                         psi*(t) = sup_L (Lt - psi(L))
                |                                               |
                |                    +--------------------------+--------------------------+
                |               Hoeffding's lemma        Bennett's lemma           (Bernstein moment
                |               psi <= L^2(b-a)^2/8      psi <= (v/b^2)(e^{Lb}-1-Lb)   condition)
                |                    |                         |                          |
                |               HOEFFDING                 BENNETT  --h(u) >= ------->  BERNSTEIN
                |                    |                         |    u^2/(2+2u/3)           |
                |                    +--------------------------+--------------------------+
                |                                               |
                |               "when does the MGF still factorize / when can
                |                we still expand moments?"
                |                                               |
                |          +------------------------+-----------+------------------------+
                |          |                        |                                    |
                |  NEGATIVE ASSOCIATION      LIMITED INDEPENDENCE                  CONDITION on a
                |  (E e^{LS} <= prod E e^{LXi}   (k-th moment method;             filtration
                |   still holds; Sec.3-5          no MGF)                              |
                +------->  verbatim)                                                 v
                                                                     MARTINGALES, DOOB MARTINGALE
                                                                     Z - EZ = sum Di,  E[Di|F_{i-1}]=0
                                                                                      |
                                                     +--------------------------------+-----------+
                                                AZUMA-HOEFFDING                             FREEDMAN
                                              (|Di| or range <= ci)               (conditional variance)
                                                     |                                        |
                                            BOUNDED DIFFERENCE                                 |
                                                McDIARMID                                     |
                                                     |                                        |
                         +---------------------------+----------------------+                 |
                    EFRON-STEIN                 TALAGRAND                SELF-BOUNDING         |
                  (true variance)             convex distance          / entropy method       |
                         |                           |                         |              |
                         +---------------------------+------------+------------+--------------+
                                                                  |
                                                                  v
                                                    STOCHASTIC TSP (the ladder)
                        McDiarmid: sqrt(n)  .  martingale+var: sqrt(log n)  .  Talagrand: O(1)

2. What "concentration" means, and why the second moment is not enough

Let $Z$ be a real random variable with $\mathbb E Z$ finite. Concentration is any statement of the form $$\mathbb P\big(|Z-\mathbb E Z|\ge t\big)\le \text{(something small in }t).$$

Markov's inequality is the only primitive tool in the whole subject: for $Y\ge 0$ and $s>0$, $\mathbb P(Y\ge s)\le \mathbb E Y/s$. Everything below — all of it — is Markov applied to a cleverly chosen $Y$.

• $Y=(Z-\mathbb E Z)^2$ gives Chebyshev: $\mathbb P(|Z-\mathbb E Z|\ge t)\le \operatorname{Var}(Z)/t^2$.
• $Y=|Z-\mathbb E Z|^k$ gives the $k$-th moment method: $\mathbb P(|Z-\mathbb E Z|\ge t)\le \mathbb E|Z-\mathbb E Z|^k/t^k$.
• $Y=e^{\lambda(Z-\mathbb E Z)}$, $\lambda>0$, gives the Chernoff method.

For $S_n=\sum_i X_i$ with independent summands, $\operatorname{Var}(S_n)=v$, Chebyshev gives $\mathbb P(|S_n-\mathbb E S_n|\ge t)\le v/t^2$ — a polynomial tail. The CLT says the truth should look like $e^{-t^2/2v}$. The entire gap between $v/t^2$ and $e^{-t^2/2v}$ is what the MGF buys you, and the price is that you must control all moments simultaneously.

3. The master tool: the Cramér–Chernoff method

Let $Z$ have $\psi_Z(\lambda)=\log\mathbb E e^{\lambda(Z-\mathbb E Z)}<\infty$ on some interval around $0$. For any $\lambda\ge 0$, Markov on $e^{\lambda(Z-\mathbb E Z)}$ gives $$\mathbb P(Z-\mathbb E Z\ge t)\le e^{-\lambda t+\psi_Z(\lambda)}.$$ Optimizing over $\lambda$: $$\boxed{\ \mathbb P(Z-\mathbb E Z\ge t)\ \le\ \exp\big(-\psi_Z^*(t)\big),\qquad \psi_Z^*(t)=\sup_{\lambda\ge0}\{\lambda t-\psi_Z(\lambda)\}.\ }$$

Two structural facts make this a machine rather than a trick:

1. $\psi$ is additive over independent summands. If $X_1,\dots,X_n$ are independent, $\psi_{S_n}=\sum_i \psi_{X_i}$. So an upper bound on each $\psi_{X_i}$ immediately gives one on $\psi_{S_n}$.
2. $\psi$ is convex, $\psi(0)=\psi'(0)=0$, $\psi''(\lambda)=\operatorname{Var}_{\mathbb P_\lambda}(Z)$ where $d\mathbb P_\lambda\propto e^{\lambda z}d\mathbb P$ is the exponential tilt. So every bound on $\psi$ is really a bound on the variance under a tilted measure. This is the recurring engine.

Two canonical $\psi$-bounds, which define two whole families:

$$\psi(\lambda)\le \tfrac{\lambda^2 v}{2}\ \ \forall\lambda\in\mathbb R \quad\Longrightarrow\quad \psi^*(t)\ge \tfrac{t^2}{2v}\quad\text{(sub-gaussian)}$$ $$\psi(\lambda)\le \tfrac{\lambda^2 v}{2(1-b\lambda)}\ \ \text{for } 0\le\lambda<1/b \quad\Longrightarrow\quad \psi^*(t)\ge \tfrac{t^2}{2(v+bt)}\quad\text{(sub-exponential)}$$

4. Hoeffding: boundedness alone

Hoeffding's lemma. If $a\le X\le b$ a.s. and $\mathbb E X=0$, then for all $\lambda\in\mathbb R$, $$\psi_X(\lambda)=\log\mathbb E e^{\lambda X}\ \le\ \frac{\lambda^2(b-a)^2}{8}.$$

The lemma says: a bounded variable is $\frac{(b-a)^2}{4}$-sub-gaussian, no matter what its distribution is. Additivity of $\psi$ then hands you the theorem for free.

Hoeffding's inequality. Let $X_1,\dots,X_n$ be independent with $a_i\le X_i\le b_i$ a.s. Then for all $t\ge0$, $$\mathbb P\big(S_n-\mathbb E S_n\ge t\big)\ \le\ \exp\!\left(\frac{-2t^2}{\sum_{i=1}^n (b_i-a_i)^2}\right),$$ and the same for the lower tail; the two-sided version costs a factor $2$.

The defect. Hoeffding is variance-blind, and it's easy to see how badly. Take $X_i\sim\mathrm{Bern}(p)$ with $p=10^{-6}$: here $b_i-a_i=1$, so Hoeffding hands you $e^{-2t^2/n}$ no matter what $p$ is — even though $\operatorname{Var}(S_n)=np(1-p)\approx 10^{-6}n$. The gaussian scale should be $\sqrt{np}$, not $\sqrt n$; Hoeffding is off by a factor of $\sqrt{1/p}=1000$ in the deviation scale. Patching this hole is the entire content of the next two sections.

5. Bennett: putting the variance back in

Bennett's lemma. Let $\mathbb E X=0$, $X\le b$ a.s., $\mathbb E X^2=\sigma^2$. Then for $\lambda>0$, $$\psi_X(\lambda)\ \le\ \frac{\sigma^2}{b^2}\big(e^{\lambda b}-1-\lambda b\big).$$

Bennett's inequality. Let $X_1,\dots,X_n$ be independent with $\mathbb E X_i=0$, $X_i\le b$ a.s., and $v=\sum_i \mathbb E X_i^2$. Then $$\boxed{\ \mathbb P(S_n\ge t)\ \le\ \exp\!\left(-\frac{v}{b^2}\,h\!\Big(\frac{bt}{v}\Big)\right),\qquad h(u)=(1+u)\log(1+u)-u.\ }$$

Sanity check on the Bernoulli example: with $X_i=\mathbb 1_i-p$, $b=1$, $v=np(1-p)$, Bennett's exponent at $t=\delta np$ recovers the classical multiplicative Chernoff bound $e^{-np\,h(\delta)}$. Hoeffding's $\sqrt n$ scale has become $\sqrt{np}$. Fixed.

Asymptotics of $h$ (the two regimes that Bernstein will exploit): $$h(u)\sim \tfrac{u^2}{2}\ (u\to0),\qquad h(u)\sim u\log u\ (u\to\infty).$$

6. Bernstein: the usable two-regime relaxation

Bennett is sharp, but $h$ is a pain to invert and nobody wants to see it in a lemma statement. Bernstein trades a constant for legibility, via the elementary inequality $$h(u)\ \ge\ \frac{u^2}{2(1+u/3)},\qquad u\ge 0.$$

Bernstein's inequality (bounded form). Independent $X_i$, $\mathbb E X_i=0$, $X_i\le b$ a.s., $v=\sum_i\mathbb E X_i^2$. Then $$\boxed{\ \mathbb P(S_n\ge t)\ \le\ \exp\!\left(-\frac{t^2}{2\big(v+\tfrac{bt}{3}\big)}\right)\ }$$ equivalently, for all $s\ge 0$, $\ \mathbb P\big(S_n\ge \sqrt{2vs}+\tfrac{bs}{3}\big)\le e^{-s}.$

The inverted form is the one to memorize; it makes the two regimes explicit:

• Gaussian regime ($t\lesssim v/b$): the exponent is $\approx -t^2/2v$. You get exactly what the CLT would suggest, non-asymptotically.
• Poisson/exponential regime ($t\gtrsim v/b$): the exponent is $\approx -3t/2b$. A linear exponent — the tail is exponential, not gaussian. This is the price of a single summand being able to carry the deviation on its own.

Bernstein's inequality (moment form). Boundedness is not needed; a moment growth condition suffices. If for all integers $k\ge 2$ $$\mathbb E |X_i|^k\ \le\ \tfrac{1}{2}\,k!\,\sigma_i^2\,b^{k-2}\qquad\text{(the Bernstein condition)},$$ then $\psi_{S_n}(\lambda)\le \frac{\lambda^2 v}{2(1-b\lambda)}$ for $0\le\lambda<1/b$ with $v=\sum_i\sigma_i^2$, and $$\mathbb P(S_n\ge t)\ \le\ \exp\!\left(-\frac{t^2}{2(v+bt)}\right).$$

This version covers sub-exponential variables (e.g. $\chi^2$, products of gaussians, quadratic forms), which have no a.s. bound at all.

6.1 Interlude: the two Orlicz classes

The whole of §4–§6 is the statement that bounded/light-tailed variables fall into one of two boxes.

Useful closure facts: sub-gaussian $\times$ sub-gaussian $=$ sub-exponential ($\|XY\|_{\psi_1}\le\|X\|_{\psi_2}\|Y\|_{\psi_2}$); sub-gaussianity is preserved under sums with variance proxies adding; $X$ bounded in $[a,b]$ $\Rightarrow$ $\sigma^2=(b-a)^2/4$. Hoeffding $=$ "bounded $\Rightarrow$ sub-gaussian"; Bernstein $=$ "bounded + small variance $\Rightarrow$ sub-gaussian near the origin, sub-exponential far out."

7. Breaking independence I: negative association

Go back and check: independence was used exactly once in §3–§6, to factorize $\mathbb E e^{\lambda S_n}=\prod_i \mathbb E e^{\lambda X_i}$. That's it. So we don't actually need independence — we need the inequality $$\mathbb E\, e^{\lambda S_n}\ \le\ \prod_{i=1}^n \mathbb E\, e^{\lambda X_i}.\tag{$\star$}$$ Negative association is precisely the hypothesis that delivers $(\star)$.

Definition. $X=(X_1,\dots,X_n)$ is negatively associated (NA) if for all disjoint $A,B\subseteq[n]$ and all increasing $f:\mathbb R^{A}\to\mathbb R$, $g:\mathbb R^{B}\to\mathbb R$ (with finite variances), $$\operatorname{Cov}\big(f(X_A),\,g(X_B)\big)\ \le\ 0.$$

Intuition: "one coordinate being large makes the others tend to be small," and this must hold robustly, for arbitrary monotone statistics of disjoint blocks — not merely pairwise.

Closure properties (Joag-Dev & Proschan, 1983). These are what make NA usable in practice:

• (N1) Independent random variables are NA (with equality in the covariance).
• (N2) Increasing functions of disjoint subsets of NA variables are NA.
• (N3) The concatenation of independent NA vectors is NA.
• (N4) If $X$ is NA then $-X$ is NA. (Because $\operatorname{Cov}(f,g)=\operatorname{Cov}(-f,-g)$, so NA also gives $\operatorname{Cov}(\text{decreasing},\text{decreasing})\le0$.)
• (N5) NA $\Rightarrow$ pairwise negative correlation $\Rightarrow$ $\operatorname{Var}(S_n)\le\sum_i\operatorname{Var}(X_i)$.

Theorem (NA $\Rightarrow$ MGF factorization). If $X$ is NA, then for every $\lambda\in\mathbb R$, $(\star)$ holds.

Where NA shows up.

The strong Rayleigh route is the deepest: a probability measure on $\{0,1\}^n$ whose generating polynomial is real stable is strong Rayleigh, and strong Rayleigh $\Rightarrow$ NA. This gives Chernoff bounds for uniform spanning trees, DPP-based samplers, and many randomized rounding schemes essentially for free.

What NA does not give you. NA rescues the Chernoff method, i.e. bounds on linear statistics. It does not automatically hand you the martingale machinery of §9–§11, so general Lipschitz functions of NA variables are not covered by anything above. Keep the scope honest.

8. Breaking independence II: limited independence

The opposite relaxation: keep the variables "independent," but only $k$ at a time.

Definition. $X_1,\dots,X_n$ are $k$-wise independent if every sub-collection of size $\le k$ is (mutually) independent.

Why care. A $k$-wise independent distribution on $\{0,1\}^n$ can be supported on a sample space of size $n^{O(k)}$ instead of $2^n$ (e.g. $X_i = \langle a_i, U\rangle$ over $\mathbb F_2$ with $U$ uniform on $\mathbb F_2^{\,m}$ and $\{a_i\}$ any $k$-wise-independent code). So a randomized algorithm using only $k$-wise independence can be derandomized by exhaustive search over $n^{O(k)}$ seeds. The whole question is: how much independence do I need to buy how strong a tail?

The MGF is dead. $\mathbb E e^{\lambda S_n}$ involves the joint law of all $n$ coordinates at once, and $k$-wise independence says nothing whatsoever about that. Neither $(\star)$ nor anything in §3–§6 survives. We're thrown back on moments.

What survives.

1. Pairwise ($k=2$) $\Rightarrow$ Chebyshev. $\operatorname{Var}(S_n)=\sum_i\operatorname{Var}(X_i)=v$ requires only pairwise independence, so $\mathbb P(|S_n-\mathbb E S_n|\ge t)\le v/t^2.$ And this is tight: there exist pairwise independent families whose tails really are only polynomial. No amount of cleverness upgrades $k=2$ to exponential.
2. The $k$-th moment method. For even $k$, $$\mathbb P(|S_n-\mathbb E S_n|\ge t)\ \le\ \frac{\mathbb E (S_n-\mathbb E S_n)^k}{t^k}.$$ Expanding $(S_n-\mathbb E S_n)^k=\sum \prod_{j} \tilde X_{i_j}$ produces only monomials in at most $k$ distinct indices. Every such expectation is computable from the $k$-wise marginals alone. So the $k$-th moment method is exactly the tool matched to $k$-wise independence — no more, no less.
3. Growing $k$ recovers Chernoff. (Schmidt–Siegel–Srinivasan, 1995.) Let $X_1,\dots,X_n\in\{0,1\}$ be $k$-wise independent, $\mu=\mathbb E S_n$, $0<\delta\le1$. If $k \ge \lceil \mu\delta^2 e^{-1/3}\rceil$, then $$\mathbb P\big(|S_n-\mu|\ge\delta\mu\big)\ \le\ e^{-\lfloor k/2\rfloor}.$$ Slogan: $\Theta(\mu\delta^2)$-wise independence buys you the full Chernoff bound $e^{-\Omega(\delta^2\mu)}$. You pay for the exponent with the order of independence, one for one. Conversely, for fixed $k$ there are $k$-wise independent families whose tails decay only polynomially (roughly $t^{-k/2}$) — so the trade is real, not an artifact of the proof.

The contrast that matters: NA is a hypothesis about monotone structure and it preserves the MGF. Limited independence is a hypothesis about low-order marginals and it preserves only low-order moments. They relax independence along orthogonal axes.

9. Martingales and Doob's construction

So far everything has been about $\sum_i X_i$. But the objects we actually care about — chromatic numbers, tour lengths, empirical suprema — are nonlinear functions $f(X_1,\dots,X_n)$. Martingales are the device that makes them linear again.

9.1 Filtrations: bookkeeping for "what I know so far"

Everything lives on a fixed probability space $(\Omega,\mathcal F,\mathbb P)$.

Definition (filtration). A filtration is a nested, increasing family of sub-$\sigma$-algebras of $\mathcal F$: $$\mathcal F_0\ \subseteq\ \mathcal F_1\ \subseteq\ \cdots\ \subseteq\ \mathcal F_n\ \subseteq\ \mathcal F,$$ i.e. each $\mathcal F_i$ is itself a $\sigma$-algebra on $\Omega$ (closed under complement and countable union, contains $\emptyset$), and $\mathcal F_{i-1}\subseteq\mathcal F_i$ for every $i\in[n]$. We always take $\mathcal F_0=\{\emptyset,\Omega\}$ trivial, so that $\mathbb E[Z\mid\mathcal F_0]=\mathbb E Z$ for every $Z\in L^1$.

The point of the definition is entirely epistemic. A $\sigma$-algebra is a catalogue of questions you are allowed to ask: $A\in\mathcal F_i$ means "by time $i$ you can tell whether the event $A$ occurred." Nestedness $\mathcal F_{i-1}\subseteq\mathcal F_i$ says information only accumulates — you never forget. And "$Y$ is $\mathcal F_i$-measurable" ($Y^{-1}(B)\in\mathcal F_i$ for Borel $B$) means "$Y$ is a quantity you can already evaluate at time $i$." A process $(Y_i)$ with $Y_i$ being $\mathcal F_i$-measurable for each $i$ is called adapted; one with $Y_i$ being $\mathcal F_{i-1}$-measurable is predictable (known one step early), which is exactly the property $A_i,B_i,V_n$ will have below.

The only filtration we actually use. Given $X_1,\dots,X_n$, the natural filtration is $$\mathcal F_i:=\sigma(X_1,\dots,X_i)=\sigma\big(\{X_j^{-1}(B): j\le i,\ B\in\mathcal A_j\}\big),$$ the smallest $\sigma$-algebra making $X_1,\dots,X_i$ measurable. Here $\mathcal F_i$ is literally "I have seen the first $i$ coordinates and nothing else," and $\mathbb E[Z\mid\mathcal F_i]$ is your best $L^2$ forecast of $Z$ given that. Note $\mathcal F_0$ is trivial (seen nothing) and $\mathcal F_n=\sigma(X)$ (seen everything), which is why $\mathbb E[f(X)\mid\mathcal F_0]=\mathbb Ef(X)$ and $\mathbb E[f(X)\mid\mathcal F_n]=f(X)$ — the two endpoints that make §9.2 work.

Two facts about conditional expectation get used below and nowhere else, so let's name them now: the tower property, $\mathbb E\big[\mathbb E[Z\mid\mathcal F_i]\mid\mathcal F_{i-1}\big]=\mathbb E[Z\mid\mathcal F_{i-1}]$ whenever $\mathcal F_{i-1}\subseteq\mathcal F_i$; and taking out what is known, $\mathbb E[YZ\mid\mathcal F_i]=Y\,\mathbb E[Z\mid\mathcal F_i]$ when $Y$ is $\mathcal F_i$-measurable (and everything is integrable). That's the entire toolkit — nothing deeper is hiding.

9.2 Martingales and the Doob construction

Definition (martingale). $(M_i)_{i=0}^n$ is a martingale with respect to $(\mathcal F_i)_{i=0}^n$ if $M_i$ is $\mathcal F_i$-measurable (adapted), $\mathbb E|M_i|<\infty$, and $$\mathbb E[M_i\mid \mathcal F_{i-1}]=M_{i-1},\qquad i\in[n].$$ The martingale difference sequence (MDS) is $D_i:=M_i-M_{i-1}$, so $\mathbb E[D_i\mid\mathcal F_{i-1}]=0$ and $M_n-M_0=\sum_{i=1}^n D_i.$

This is the point: any martingale is a sum of terms that are conditionally centered. Conditionally centered is all the Chernoff method ever needed.

Doob martingale (the universal construction). Fix any $Z\in L^1$ and any filtration $(\mathcal F_i)$. Define $M_i := \mathbb E[Z\mid \mathcal F_i].$ The tower property gives $\mathbb E[M_i|\mathcal F_{i-1}]=\mathbb E[Z|\mathcal F_{i-1}]=M_{i-1}$, so $(M_i)$ is a martingale, with $M_0=\mathbb E Z$ and $M_n=Z$ if $Z$ is $\mathcal F_n$-measurable. Therefore $$\boxed{\ Z-\mathbb E Z=\sum_{i=1}^n D_i,\qquad D_i=\mathbb E[Z\mid\mathcal F_i]-\mathbb E[Z\mid\mathcal F_{i-1}].\ }$$

It's worth sitting with that for a second: every integrable random variable is a sum of martingale differences — in as many ways as there are filtrations. Concentration of $Z$ has been reduced to controlling increments, and increments are conditionally centered, which is all §3–§6 ever asked for. If you take one structural idea away from this post, take this one.

Exposure martingale. For $Z=f(X_1,\dots,X_n)$ take $\mathcal F_i=\sigma(X_1,\dots,X_i)$: $D_i$ is "the revision to my forecast of $f$ upon learning $X_i$." The martingale reveals the randomness one coordinate at a time.

10. Azuma–Hoeffding and Freedman

The move: apply Hoeffding's/Bennett's lemma conditionally on $\mathcal F_{i-1}$, then peel off one factor at a time with the tower property.

Azuma–Hoeffding. Let $(M_i)_{i=0}^n$ be a martingale with $|D_i|\le c_i$ a.s. Then $$\mathbb P(M_n-M_0\ge t)\ \le\ \exp\!\left(\frac{-t^2}{2\sum_{i=1}^n c_i^2}\right).$$

Azuma with conditional range (the sharp version). Suppose there are $\mathcal F_{i-1}$-measurable $A_i\le B_i$ with $A_i\le D_i\le B_i$ a.s. and $B_i-A_i\le c_i$. Then $$\boxed{\ \mathbb P(M_n-M_0\ge t)\ \le\ \exp\!\left(\frac{-2t^2}{\sum_{i=1}^n c_i^2}\right).\ }$$

Note the bookkeeping: the crude hypothesis $|D_i|\le c_i$ means the range is $2c_i$, which is why it loses a factor of $4$ in the exponent relative to the conditional-range version. Always use the range.

Freedman's inequality (= Bernstein for martingales). Let $D_i\le b$ a.s. and let the predictable quadratic variation be $V_n:=\sum_{i=1}^n \mathbb E[D_i^2\mid \mathcal F_{i-1}].$ Then for all $t,v\ge0$, $$\mathbb P\big(M_n-M_0\ge t,\ V_n\le v\big)\ \le\ \exp\!\left(\frac{-t^2}{2(v+bt/3)}\right).$$ (Proof: identical peeling, but with Bennett's lemma conditionally, tracking $\sum_i \mathbb E[D_i^2|\mathcal F_{i-1}]$ as a supermartingale rather than bounding it term by term.)

The parallelism is exact and worth internalizing:

Freedman is the variance-aware tool, and just as in §5, the variance-awareness is where the good bounds live. This is exactly the gap that the TSP will expose.

11. The bounded difference condition and McDiarmid's inequality

Now specialize the Doob martingale to functions of independent coordinates and ask the obvious question: what hypothesis on $f$ makes the increments have small range? The answer is about as simple as you could hope for.

Definition (Bounded Difference Condition, BDC). $f:\mathcal X\to\mathbb R$ satisfies the BDC with constants $c_1,\dots,c_n\ge 0$ if for every $i\in[n]$, $$\sup_{x\in\mathcal X}\ \sup_{y\in\mathcal X_i}\ \big|f(x)-f(x^{\,i\leftarrow y})\big|\ \le\ c_i.$$ In words: changing one coordinate, however you like, moves $f$ by at most $c_i$. ($f$ is $c_i$-Lipschitz in coordinate $i$ w.r.t. the discrete metric.)

McDiarmid's inequality (bounded differences). Let $X_1,\dots,X_n$ be independent and $f$ satisfy the BDC with constants $c_i$. Then for all $t\ge0$, $$\boxed{\ \mathbb P\big(f(X)-\mathbb E f(X)\ge t\big)\ \le\ \exp\!\left(\frac{-2t^2}{\sum_{i=1}^n c_i^2}\right)\ }$$ and symmetrically for the lower tail (factor $2$ for two-sided).

Consistency check. $f(x)=\sum_i x_i$ with $x_i\in[a_i,b_i]$ satisfies the BDC with $c_i=b_i-a_i$, and McDiarmid returns exactly Hoeffding's inequality, constants included. McDiarmid is Hoeffding, conditionalized. That is the whole content.

Worked example (chromatic number). $G\sim G(n,p)$, $f=\chi(G)$, vertex exposure: revealing vertex $i$'s edges to $\{1,\dots,i-1\}$ can change $\chi$ by at most $1$ (recolor that vertex with a fresh color). So $c_i=1$, $\sum c_i^2=n$, and $$\mathbb P\big(|\chi(G)-\mathbb E\chi(G)|\ge t\big)\le 2e^{-2t^2/n}:$$ $\chi(G(n,p))$ is concentrated in a window of width $O(\sqrt n)$ — without knowing $\mathbb E\chi$ at all (Shamir–Spencer). Concentration is decoupled from computation. Hold on to this; it is the moral of §13 too.

12. What McDiarmid misses, and the four repairs

The defect: McDiarmid is variance-blind, exactly as Hoeffding was — which shouldn't surprise anyone, since McDiarmid is Hoeffding. Its effective variance proxy is $\frac14\sum_i c_i^2$, a worst-case quantity, and the truth can be smaller by any factor you like.

Repair 1 — Efron–Stein (the exact variance). For independent $X_i$ and $f(X)\in L^2$: $$\operatorname{Var}\big(f(X)\big)\ \le\ \tfrac12\sum_{i=1}^n\mathbb E\Big[\big(f(X)-f(X^{\,i\leftarrow X_i'})\big)^2\Big] \ =\ \sum_{i=1}^n \mathbb E\big[\operatorname{Var}_i(f)\big],$$ where $\operatorname{Var}_i$ is the variance in $X_i$ alone. Equivalently, since $\mathbb E[f\mid X_{-i}]$ is the $L^2$-projection, for any measurable $g_i$ of the other coordinates: $$\operatorname{Var}\big(f(X)\big)\ \le\ \sum_{i=1}^n\mathbb E\Big[\big(f(X)-g_i(X_{-i})\big)^2\Big].\tag{ES}$$ The BDC gives $\operatorname{Var}(f)\le\frac14\sum_ic_i^2$ — precisely McDiarmid's proxy. So Efron–Stein is the second-moment shadow of McDiarmid, and any gap between (ES) and $\frac14\sum c_i^2$ is a gap McDiarmid is throwing away. (ES) is the cheapest possible diagnostic: compute it first, always.

Repair 2 — self-bounding functions (Boucheron–Lugosi–Massart). If there exist $f_i(x_{-i})$ with $$0\le f(x)-f_i(x_{-i})\le 1\quad\text{and}\quad \sum_{i=1}^n\big(f(x)-f_i(x_{-i})\big)\le f(x)\quad\forall x,$$ then (ES) gives $\operatorname{Var}(f)\le\mathbb E f$ and moreover a Bernstein-type tail $$\mathbb P\big(f\ge \mathbb E f+t\big)\le \exp\!\left(\frac{-t^2}{2\mathbb E f+2t/3}\right),\qquad \mathbb P\big(f\le \mathbb E f-t\big)\le \exp\!\left(\frac{-t^2}{2\mathbb E f}\right).$$ The variance proxy is $\mathbb E f$, not $n$. Covers configuration functions, VC entropy, Rademacher complexity, many combinatorial counts.

Repair 3 — Talagrand's convex distance inequality. For $x\in\mathcal X$, $A\subseteq\mathcal X$, define $$d_T(x,A):=\sup_{\alpha\in\mathbb R^n_{\ge0},\ \|\alpha\|_2\le 1}\ \inf_{y\in A}\ \sum_{i=1}^n \alpha_i\,\mathbb 1\{x_i\ne y_i\}.$$ Then for independent coordinates, $$\mathbb E\Big[e^{d_T(X,A)^2/4}\Big]\ \le\ \frac{1}{\mathbb P(X\in A)}\qquad\Longrightarrow\qquad \mathbb P(X\in A)\cdot\mathbb P\big(d_T(X,A)\ge t\big)\le e^{-t^2/4}.$$ This is an isoperimetric statement in product spaces: the Hamming weights $\alpha$ are chosen adversarially after seeing $x$, which lets the bound adapt to which coordinates actually matter for $x$. That adaptivity is exactly the variance-awareness McDiarmid lacks. Functions that are Lipschitz w.r.t. $d_T$ — convex Lipschitz functions, and more generally certifiable / configuration functions, where a value of $f(x)$ is witnessed by a small subset of coordinates — concentrate at the scale of $\sqrt{\text{witness size}}$, not $\sqrt n$.

Repair 4 — the entropy method. Replace $\psi$ with the entropy functional $\operatorname{Ent}(e^{\lambda f})=\mathbb E[\lambda f e^{\lambda f}]-\mathbb E[e^{\lambda f}]\log\mathbb E[e^{\lambda f}]$ and use sub-additivity of entropy over independent coordinates plus a modified log-Sobolev inequality. This tensorizes without any martingale and recovers McDiarmid, the self-bounding bound, and most Talagrand-type results in a single framework (Boucheron–Lugosi–Massart, Concentration Inequalities, 2013). It is the "right" modern proof, but the martingale route is the right mental route, so I keep it primary here.

13. The finale: the stochastic travelling salesman problem

Everything above now gets stress-tested on a single object, and — this is the fun part — most of it fails.

13.1 Setup

Let $X_1,\dots,X_n$ be i.i.d. $\mathrm{Unif}([0,1]^2)$. For $x=(x_1,\dots,x_n)\in([0,1]^2)^n$ define the optimal closed tour length $$L(x)\ :=\ \min_{\sigma\in S_n}\ \sum_{i=1}^{n}\big\|x_{\sigma(i)}-x_{\sigma(i+1)}\big\|_2,\qquad \sigma(n+1):=\sigma(1),$$ and write $L_n:=L(X_1,\dots,X_n)$. Computing $L(x)$ is NP-hard. Computing $\mathbb E L_n$ is, as far as anyone knows, hopeless in closed form. We will nonetheless pin down $L_n$ to within $O(1)$.

13.2 Two geometric lemmas (the only geometry we need)

Let $d_i(x):=\min_{j\ne i}\|x_i-x_j\|_2$ be the nearest-neighbour distance of point $i$.

(G1) Monotonicity + insertion cost. $$0\ \le\ L(x)-L(x_{-i})\ \le\ 2\,d_i(x).$$

(G2) Nearest-neighbour scale. For $X_i$ i.i.d. uniform on $[0,1]^2$, $\mathbb P(d_i>r)\approx (1-\pi r^2)^{n-1}\approx e^{-\pi r^2 n}$, hence $$\mathbb E\big[d_i^2\big]=\int_0^\infty \mathbb P(d_i^2>s)\,ds \ \asymp\ \int_0^\infty e^{-\pi s n}ds\ =\ \Theta(1/n).$$

(G3) The space-filling bound. Any $m$ points in a square of side $\ell$ admit a tour of length $\le C\ell\sqrt m$ (snake through a $\sqrt m\times\sqrt m$ grid of cells). This is the source of all $\sqrt{n}$'s below.

13.3 The law of large numbers: BHH

Theorem (Beardwood–Halton–Hammersley, 1959). There is a constant $\beta_{\mathrm{TSP}}\in(0,\infty)$ with $$\frac{L_n}{\sqrt n}\ \xrightarrow[n\to\infty]{}\ \beta_{\mathrm{TSP}}\qquad\text{a.s. and in }L^1.$$ More generally, if $X_i\overset{\text{iid}}{\sim} f$ with compact support, $L_n/\sqrt n\to \beta_{\mathrm{TSP}}\int f(x)^{1/2}dx$ a.s.

$\beta_{\mathrm{TSP}}\approx 0.7124$ numerically; no closed form is known. The proof is the theory of subadditive Euclidean functionals (Steele): $L$ is (i) geometrically subadditive over a partition of the square into subsquares (up to boundary corrections), (ii) smooth in the sense of (G1), (iii) homogeneous of degree 1. Then Kingman-type subadditivity gives the limit. So: $\mathbb E L_n \asymp \sqrt n$. Remember that scale.

13.4 Rung 1 — McDiarmid, and why it is vacuous

$L$ satisfies the BDC. Moving one point anywhere in $[0,1]^2$ changes $L$ by at most $O(1)$ (delete and reinsert, using (G1) with $d_i\le\sqrt2$): take $c_i=4\sqrt2$. Then $\sum_i c_i^2=32n$ and $$\mathbb P\big(|L_n-\mathbb E L_n|\ge t\big)\ \le\ 2\exp\!\big(-t^2/(16n)\big).$$ This is a true statement and it is useless: it only becomes nontrivial at $t\asymp\sqrt n$, which is the same order as $\mathbb E L_n$ itself. It does not even reprove the law of large numbers.

13.5 Rung 2 — Efron–Stein: the variance is already $O(1)$

Apply (ES) with $g_i(x_{-i}):=L(x_{-i})$, then (G1) and (G2):

$$\operatorname{Var}(L_n)\ \le\ \sum_{i=1}^n \mathbb E\big[(L_n-L(X_{-i}))^2\big]\ \le\ \sum_{i=1}^n \mathbb E\big[4\,d_i^2\big]\ =\ n\cdot O(1/n)\ =\ \boxed{O(1)}.$$

(Steele, 1981.) Read that again, because it's the whole point: $\mathbb E L_n\asymp\sqrt n$ but $\operatorname{Var}(L_n)=O(1)$, uniformly in $n$. The fluctuations don't grow at all. McDiarmid's proxy overstated the variance by a factor of $n$, and it took three lines to find out. So now we know what to hope for — a dimension-free sub-gaussian tail — and we know the deficiency is McDiarmid's, not the problem's.

13.6 Rung 3 — the martingale, done properly: $\sqrt{\log n}$

Use the exposure martingale $M_i=\mathbb E[L_n\mid X_{1:i}]$, $D_i=M_i-M_{i-1}$. The key insight is that the increments are not equally important:

• Early increments ($i$ small): $n-i$ points are still unrevealed, so $X_i$ will end up with a nearest neighbour at distance $\Theta((n-i)^{-1/2})$, and by (G1) its marginal influence on $\mathbb E[L\mid\cdot]$ is $O((n-i)^{-1/2})$ — tiny.
• Late increments ($i\approx n$): few points remain, influence is $O(1)$ — but there are few such steps.

Quantitatively, one shows $\mathbb E[D_i^2\mid\mathcal F_{i-1}]\ \lesssim\ \frac{C}{n-i+1}$ a.s., while only the crude a.s. bound $|D_i|=O(1)$ holds. So use Freedman, not Azuma: $$V_n=\sum_{i=1}^n\mathbb E[D_i^2\mid\mathcal F_{i-1}]\ \lesssim\ \sum_{i=1}^n\frac{C}{n-i+1}\ =\ C\,H_n\ =\ O(\log n),$$ giving, in the gaussian regime, $$\mathbb P\big(|L_n-\mathbb E L_n|\ge t\big)\ \le\ 2\exp\!\left(\frac{-c\,t^2}{\log n}\right)\qquad\text{i.e. fluctuations } O(\sqrt{\log n}).$$ (Rhee–Talagrand, 1987, "Martingale inequalities and NP-complete problems.")

This is the payoff for everything in §9–§10 at once: the Doob martingale + a smart exposure order + the variance-aware (Freedman/Bennett) inequality instead of the variance-blind (Azuma/Hoeffding) one. We went from $\sqrt n$ to $\sqrt{\log n}$. But Efron–Stein already told us the answer should be $O(1)$, so a $\sqrt{\log n}$ remains — and it is a genuine artifact of the martingale method: the harmonic sum $\sum_i \frac1{n-i+1}$ is inherent to revealing coordinates one at a time in a fixed order.

13.7 Rung 4 — the sharp result: dimension-free sub-gaussian

Theorem (Rhee–Talagrand, 1989; see also Talagrand, 1995). There is a universal constant $C<\infty$ such that for all $n\ge1$ and all $t\ge0$, $$\boxed{\ \mathbb P\big(|L_n-\mathbb E L_n|\ge t\big)\ \le\ C\exp\!\big(-t^2/C\big).\ }$$

No $n$. No $\log n$. $L_n$ is $O(1)$-sub-gaussian around a mean of order $\sqrt n$, forever. (With a bound of this shape, mean and median are interchangeable at cost $O(1)$, so it doesn't matter which you center at.)

The proof abandons the martingale and uses Talagrand's convex distance / isoperimetry in product spaces (Repair 3 of §12). The structural input the TSP supplies is a certification property: a short tour on a point set is witnessed by local structure, and by (G3) any $m$ points confined to a square of side $\ell$ can be toured in $\le C\ell\sqrt m$. So if $X$ disagrees with a "good" configuration $y\in A$ on a set of coordinates of small weighted size, the tour can be repaired at cost controlled by $\sqrt{\text{that size}}$ — which is exactly the $\|\alpha\|_2\le1$ / $d_T$ geometry. The adversarial choice of $\alpha$ in $d_T$ is what lets the bound say "only the coordinates that actually mattered count," which is precisely what the fixed exposure order of the martingale could not express.

13.8 The ladder, in one table

14. Cheat sheet

Independent (or NA) real $X_i$, $S_n=\sum_i X_i$, $\tilde X_i = X_i - \mathbb E X_i$:

Dependence:

Nonlinear $f$, martingale $M_i=\mathbb E[Z|\mathcal F_i]$, $D_i=M_i-M_{i-1}$:

References worth citing

• Boucheron, Lugosi, Massart, Concentration Inequalities: A Nonasymptotic Theory of Independence (2013) — the canonical reference for §3–§12.
• Joag-Dev & Proschan, Negative association of random variables with applications, Ann. Statist. (1983); Dubhashi & Ranjan, Balls and bins: a study in negative dependence, RSA (1998).
• Borcea, Brändén, Liggett, Negative dependence and the geometry of polynomials, JAMS (2009).
• Schmidt, Siegel, Srinivasan, Chernoff–Hoeffding bounds for applications with limited independence, SIAM J. Discrete Math. (1995).
• Freedman, On tail probabilities for martingales, Ann. Probab. (1975).
• McDiarmid, On the method of bounded differences, Surveys in Combinatorics (1989).
• Steele, Subadditive Euclidean functionals and nonlinear growth in geometric probability, Ann. Probab. (1981); and Probability Theory and Combinatorial Optimization (1997).
• Beardwood, Halton, Hammersley, The shortest path through many points, Proc. Camb. Phil. Soc. (1959).
• Rhee & Talagrand, Martingale inequalities and NP-complete problems, Math. Oper. Res. (1987); A sharp deviation inequality for the stochastic traveling salesman problem, Ann. Probab. (1989).
• Talagrand, Concentration of measure and isoperimetric inequalities in product spaces, IHÉS Publ. Math. (1995).