# McDiarmid's inequality
**McDiarmid's inequality**, also called the bounded differences inequality, is a [concentration inequality](https://www.edgepedia.org/concentration-inequality) in probability theory stating that a function of independent random variables concentrates sharply around its expected value whenever changing any single input can move the function's value by only a bounded amount. It was published by Colin McDiarmid, a mathematician at Oxford University, in his 1989 survey "On the method of bounded differences".[1](https://www.cambridge.org/core/books/abs/surveys-in-combinatorics-1989/on-the-method-of-bounded-differences/AABA597B562BDA7D89C6077E302694FB)
| Key fact | Detail |
|---|---|
| Hypothesis | Independent random variables \( X_1,\ldots,X_n \) and a function \( f \) whose value changes by at most \( c_i \) when only coordinate \( i \) is changed[2](https://androma.org/theorems/6074) |
| One-sided bound | \( \mathbf{P}[X-\mathbf{E}[X]\ge t] \le \exp\!\left(-\frac{2t^2}{\sum_i c_i^2}\right) \), and the same for the lower tail[3](https://www.cl.cam.ac.uk/teaching/1819/Probablty/materials/Lecture7.pdf) |
| Two-sided bound | \( \mathbf{P}(|X-\mathbf{E}[X]|\ge t) \le 2\exp\!\left(-\frac{2t^2}{C}\right) \) with \( C=\sum_{i=1}^n c_i^2 \)[2](https://androma.org/theorems/6074) |
| Proof route | The Doob martingale \( Z_i=\mathbf{E}[f(X_1,\ldots,X_n)\mid X_1,\ldots,X_i] \) has increments bounded by \( c_i \), so Azuma–Hoeffding applies[4](https://www.kunisky.com/static/teaching/2026spring-prob2/prob2-notes-2026.pdf) |
| Special case | For a sum of independent variables with \( X_j\in[a_j,b_j] \), it reduces to Hoeffding's bound \( \exp(-2t^2/\sum_j (b_j-a_j)^2) \)[5](https://unseel.com/mathematics/mcdiarmid-inequality) |
| Typical applications | Number of empty bins in a balls-and-bins experiment, chromatic numbers of random graphs, and generalization bounds in statistical learning theory[3](https://www.cl.cam.ac.uk/teaching/1819/Probablty/materials/Lecture7.pdf) • [6](https://arxiv.org/abs/1301.0579) |
## Statement
Let \( X_1,\ldots,X_n \) be independent random variables, with \( X_i \) taking values in a measurable space \( \mathcal{X}_i \), and let \( f:\mathcal{X}_1\times\cdots\times\mathcal{X}_n\to\mathbb{R} \) satisfy the bounded differences condition: there are nonnegative constants \( c_1,\ldots,c_n \) such that whenever two inputs \( x \) and \( x' \) differ only in coordinate \( i \),
\[ |f(x)-f(x')| \le c_i. \]
The constant \( c_i \) is a discrete, worst-case notion of derivative with respect to the \( i \)-th coordinate: it measures how much \( f \) can possibly change when input \( i \) is altered arbitrarily.[4](https://www.kunisky.com/static/teaching/2026spring-prob2/prob2-notes-2026.pdf) Writing \( X=f(X_1,\ldots,X_n) \) and \( C=\sum_{i=1}^n c_i^2 \), the inequality states that for every \( t\ge 0 \),
\[ \mathbf{P}[X-\mathbf{E}[X]\ge t]\ \le\ \exp\!\left(-\frac{2t^2}{C}\right), \qquad \mathbf{P}[X-\mathbf{E}[X]\le -t]\ \le\ \exp\!\left(-\frac{2t^2}{C}\right), \]
and, by the union bound on the two tails,
\[ \mathbf{P}\bigl(|X-\mathbf{E}[X]|\ge t\bigr)\ \le\ 2\exp\!\left(-\frac{2t^2}{C}\right). \]
The result holds for discrete random variables and can be proven for continuous ones as well.[3](https://www.cl.cam.ac.uk/teaching/1819/Probablty/materials/Lecture7.pdf) The deviation scale is set by \( \sqrt{C} \): the probability of a deviation of size \( t \) decays exponentially in \( t^2/C \), so a function that depends weakly on each of many inputs is tightly concentrated even though no individual variable is small.
## Proof idea
The standard proof builds the Doob martingale that reveals the inputs one at a time:
\[ Z_i = \mathbf{E}[f(X_1,\ldots,X_n)\mid X_1,\ldots,X_i], \qquad i=0,1,\ldots,n. \]
Here \( Z_n=f(X_1,\ldots,X_n) \) and \( Z_0=\mathbf{E}[f(X_1,\ldots,X_n)] \), so the quantity of interest is the total drift \( Z_n-Z_0 \).[3](https://www.cl.cam.ac.uk/teaching/1819/Probablty/materials/Lecture7.pdf) To bound the increments, take independent copies \( X'_1,\ldots,X'_n \) of the inputs and write \( X^{(i)}=(X_1,\ldots,X_{i-1},X'_i,X_{i+1},\ldots,X_n) \), the original vector with coordinate \( i \) resampled. Then
\[ Z_i-Z_{i-1} = \mathbf{E}[f(X)-f(X^{(i)})\mid X_1,\ldots,X_i], \]
so \( |Z_i-Z_{i-1}|\le c_i \) almost surely.[4](https://www.kunisky.com/static/teaching/2026spring-prob2/prob2-notes-2026.pdf) Applying the Azuma–Hoeffding inequality to this bounded-difference martingale gives the exponential tail; the upper tail follows from [Markov's inequality](https://www.edgepedia.org/markovs-inequality) and optimization over the exponential parameter, and applying the same argument to \( -f \) gives the lower tail.[2](https://androma.org/theorems/6074)
## Relation to Hoeffding and Azuma
The underlying martingale inequality was discovered first by [Wassily Hoeffding](https://www.edgepedia.org/wassily-hoeffding) and again independently by [Kazuoki Azuma](https://www.edgepedia.org/kazuoki-azuma), both mainly concerned with sums of uncorrelated random variables. In the late 1980s a number of researchers, including [Michel Talagrand](https://www.edgepedia.org/michel-talagrand) and McDiarmid, realized that the Azuma–Hoeffding inequality had important implications for nonlinear functions of bounded random variables.[7](https://www.stat.uchicago.edu/~lalley/Courses/313/Concentration.pdf) McDiarmid's contribution was to identify the bounded-differences hypothesis as a clean, checkable condition that supplies the required increment bounds for the Doob martingale.[5](https://unseel.com/mathematics/mcdiarmid-inequality) For this reason the result is also known as the Hoeffding–Azuma inequality in some literature.[8](https://arxiv.org/abs/1212.5796)
When \( f \) is a sum \( f(x)=\sum_j x_j \) of independent variables with \( X_j\in[a_j,b_j] \), changing coordinate \( j \) moves \( f \) by at most \( b_j-a_j \), so \( c_j=b_j-a_j \) and McDiarmid's bound becomes exactly [Hoeffding's inequality](https://www.edgepedia.org/hoeffdings-inequality) \( \exp(-2t^2/\sum_j (b_j-a_j)^2) \).[5](https://unseel.com/mathematics/mcdiarmid-inequality) The inequality is therefore a genuine extension of Hoeffding's bound from linear functions to arbitrary functions satisfying per-coordinate Lipschitz conditions.
## Applications
**Balls and bins.** Throw \( m \) balls independently and uniformly at random into \( n \) bins, and let \( F \) be the number of empty bins. Moving a single ball from one bin to another changes the count of empty bins by at most 1, so each \( c_i=1 \) and \( C=m \). McDiarmid's inequality gives
\[ \mathbf{P}[|F-\mathbf{E}[F]|>t]\ \le\ 2e^{-2t^2/m}, \]
so the number of empty bins is \( n(1-1/n)^m \pm O(\sqrt{m}) \) with high probability.[3](https://www.cl.cam.ac.uk/teaching/1819/Probablty/materials/Lecture7.pdf) • [4](https://www.kunisky.com/static/teaching/2026spring-prob2/prob2-notes-2026.pdf) The same technique applies to bin packing with random item sizes in \([0,1]\).[3](https://www.cl.cam.ac.uk/teaching/1819/Probablty/materials/Lecture7.pdf)
**Random graphs.** The method is a standard tool for proving sharp concentration of graph parameters such as the chromatic number, since exposing or changing one edge indicator changes the chromatic number by at most 1.[9](https://d-nb.info/1344908020/34) McDiarmid's own survey points to random graphs and the probabilistic analysis of algorithms as the main fields of use.[10](https://www.math.cmu.edu/~af1p/Texfiles/monotone.pdf)
**Learning theory.** In statistical learning theory, McDiarmid's inequality converts stability of a learning algorithm under changing one training example into bounds on the generalization error; in the PAC setting, an approach based on training stability bounds generalization error directly via an extended McDiarmid inequality, without reference to uniform convergence or [VC dimension](https://www.edgepedia.org/vc-dimension).[6](https://arxiv.org/abs/1301.0579)
## Extensions
The independence assumption and the worst-case constants can both be relaxed. For learning problems in which examples are dependent and their dependency relation is characterized by a graph, McDiarmid-type inequalities for Lipschitz functions of graph-dependent random variables show that concentration is governed by the forest complexity of the graph; for many types of dependent data this complexity is small, giving good concentration and stability bounds for learning from non-i.i.d. data.[11](https://papers.neurips.cc/paper_files/paper/2019/hash/658bbbdef9415ba5e2ff857f1146ba6e-Abstract.html) A related extension under graph-dependence replaces \( C \) by \( \chi_f(G)\,\|\mathbf{c}\|_2^2 \), where \( \chi_f(G) \) is the fractional chromatic number of the dependency graph \( G \).[12](https://www.sciencedirect.com/science/article/abs/pii/S0167715221002340)
A second line of work weakens the bounded-differences hypothesis itself. The entropy method of [Boucheron](https://www.edgepedia.org/boucheron), Lugosi, and Massart yields exponential concentration for self-bounding functions, whose squared coordinate changes need only be controlled by the function's value rather than by a fixed constant, a much milder requirement.[13](https://imechanica.egr.uh.edu/sites/default/files/ConcentrationOfMeasureLugosi.pdf) Other refinements include the method of typical bounded differences, which establishes sharp concentration when \( f \) does not depend too much on any of the variables only in a typical sense,[8](https://arxiv.org/abs/1212.5796) extensions in which the differences are bounded only with high probability,[14](https://newtraell.cs.uchicago.edu/research/publications/techreports/TR-2002-04) and distribution-dependent McDiarmid-type inequalities for functions of unbounded interaction.[15](https://proceedings.mlr.press/v202/li23t.html)
## References
1. [Colin McDiarmid (1989). On the method of bounded differences. Surveys in Combinatorics, 1989, London Math. Soc. Lecture Notes 141, pp. 148–188, Cambridge University Press.](https://www.cambridge.org/core/books/abs/surveys-in-combinatorics-1989/on-the-method-of-bounded-differences/AABA597B562BDA7D89C6077E302694FB)
2. [McDiarmid Bounded Differences Inequality — Statement & Proof, Androma](https://androma.org/theorems/6074)
3. [Lecture 7: Martingales and Concentration, University of Cambridge](https://www.cl.cam.ac.uk/teaching/1819/Probablty/materials/Lecture7.pdf)
4. [Lecture Notes: Probability Theory II](https://www.kunisky.com/static/teaching/2026spring-prob2/prob2-notes-2026.pdf)
5. [McDiarmid's Bounded Differences Inequality, Unseel](https://unseel.com/mathematics/mcdiarmid-inequality)
6. [Almost-everywhere algorithmic stability and generalization error, arXiv:1301.0579](https://arxiv.org/abs/1301.0579)
7. [Concentration Inequalities, University of Chicago lecture notes](https://www.stat.uchicago.edu/~lalley/Courses/313/Concentration.pdf)
8. [On the method of typical bounded differences, arXiv:1212.5796](https://arxiv.org/abs/1212.5796)
9. [Colorings of Randomly Augmented Graphs](https://d-nb.info/1344908020/34)
10. [A note citing Bollobás and McDiarmid surveys on martingale methods](https://www.math.cmu.edu/~af1p/Texfiles/monotone.pdf)
11. [McDiarmid-Type Inequalities for Graph-Dependent Variables and Stability Bounds, NeurIPS 2019](https://papers.neurips.cc/paper_files/paper/2019/hash/658bbbdef9415ba5e2ff857f1146ba6e-Abstract.html)
12. [When Janson meets McDiarmid: Bounded difference inequalities under graph-dependence, ScienceDirect](https://www.sciencedirect.com/science/article/abs/pii/S0167715221002340)
13. [Concentration-of-measure inequalities, Gábor Lugosi lecture notes](https://imechanica.egr.uh.edu/sites/default/files/ConcentrationOfMeasureLugosi.pdf)
14. [Extensions to McDiarmid's inequality when differences are bounded with high probability, University of Chicago TR-2002-04](https://newtraell.cs.uchicago.edu/research/publications/techreports/TR-2002-04)
15. [Distribution-dependent McDiarmid-type Inequalities for Functions of Unbounded Interaction, ICML 2023](https://proceedings.mlr.press/v202/li23t.html)
---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Statistics and probability › Probability theory › Expectation, moments, and inequalities › Concentration inequalities*
*Initially written Sep 17, 2026 · Reviewed: Sep 30, 2026; Oct 15, 2026 · Edited: Sep 30, 2026; Oct 15, 2026 · Last review: Oct 15, 2026*
*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*
License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license