McDiarmid’s inequality

1 Introduction to concentration inequalities

1.1 Motivation and problem setup

Concentration inequalities describe how a random quantity typically stays close to its mean (or another central value) despite randomness. A standard setup considers a function \[ f(X_1,\dots,X_n) \] of independent random variables \(X_1,\dots,X_n\), and seeks bounds on the probability that \(f\) deviates from \(\mathbb{E}f(X_1,\dots,X_n)\) by more than a specified amount. Such results provide tail probabilities without requiring full distributional knowledge.

Concentration tools include Markov-type bounds (often loose), Chernoff/Hoeffding inequalities for sums of bounded variables, and more general martingale-based results. McDiarmid’s inequality sits in a family of “bounded differences” principles: instead of requiring additive structure, it uses a sensitivity property of the function \(f\) when a single input coordinate is changed.

1.3 When McDiarmid’s inequality is applicable

It applies when:

the inputs \(X_1,\dots,X_n\) are independent (not necessarily identically distributed);
the function \(f\) satisfies a bounded-differences condition, meaning each coordinate has limited impact on the function value;
one can identify constants \(c_i\) controlling how much \(f\) can change by altering \(X_i\), holding the other coordinates fixed.

This makes McDiarmid especially useful for statistics and learning algorithms that can be shown to have limited per-sample influence.

2 Statement of McDiarmid’s inequality

2.1 Bounded differences condition

2.1.1 Measuring sensitivity to input changes

Let \(X_1,\dots,X_n\) be independent random variables taking values in measurable spaces. Consider a measurable function \(f\) of the vector \(X=(X_1,\dots,X_n)\). The bounded differences condition postulates that for each index \(i\), there exists a constant \(c_i \ge 0\) such that changing only the \(i\)-th coordinate cannot alter \(f\) by more than \(c_i\): \[

\sup_{x_1,\dots,x_n,\,x_i'} \left	f(x_1,\dots,x_i,\dots,x_n)-f(x_1,\dots,x_i',\dots,x_n)\right	\le c_i.

\] Conceptually, \(c_i\) quantifies the influence of the \(i\)-th sample on the output.

2.1.2 Choosing the bounded constants

In applications, \(c_i\) is often derived from algebraic or geometric properties:

If \(f\) is an average of bounded terms, coordinate changes shift the average by at most a scaled constant.
If \(f\) involves a maximum or minimum, one uses the fact that one coordinate can move the extremum by at most the coordinate’s bounded effect.
If \(f\) is Lipschitz with respect to a metric that changes by a controlled amount when a single coordinate changes, the corresponding Lipschitz constant yields \(c_i\).

Tight bounds improve the resulting tail estimate; loose bounds remain valid but may be weak.

2.2 Formal inequality and tail bound form

Under the bounded differences condition, McDiarmid’s inequality states that for every \(t>0\), \[ \Pr\left( f(X_1,\dots,X_n) - \mathbb{E}f(X_1,\dots,X_n) \ge t \right) \le \exp\left( \frac{-2t^2}{\sum_{i=1}^n c_i^2} \right), \] and similarly, \[

\Pr\left( \left	f(X_1,\dots,X_n) - \mathbb{E}f(X_1,\dots,X_n)\right	\ge t \right)

\le 2\exp\left( \frac{-2t^2}{\sum_{i=1}^n c_i^2} \right). \] The bound depends on the squared sensitivity summary \(\sum_i c_i^2\) rather than on the full distribution of the inputs.

2.3 Interpretation of the bound (sub-Gaussian behavior)

The exponential form \(\exp(-\text{const}\cdot t^2)\) indicates sub-Gaussian concentration. Informally, \(f(X)\) has tails comparable to those of a Gaussian random variable with variance proxy \(\frac{1}{2}\sum_i c_i^2\). This “quadratic exponent” behavior is a key reason the inequality is popular for deriving confidence bounds.

3 Conditions and assumptions

3.1 Independence of random variables

Independence is central to the martingale and conditional-expectation steps used in common proofs. If the inputs are dependent, bounded-differences concentration may fail or require different tools tailored to the dependence structure.

3.2 Measurability and integrability requirements

The function \(f\) is assumed measurable so that \(\mathbb{E}f\) exists. The bounded differences condition also implies a form of integrability because it restricts the range of changes induced by each coordinate. In typical formal treatments, it is enough that \(\mathbb{E}	f(X)	<\infty\) together with the bounded differences property.

3.3 Finite-sample considerations

For finite \(n\), the inequality provides non-asymptotic probability bounds. As \(n\) grows, the denominator \(\sum_i c_i^2\) often scales like \(n\) (for comparable \(c_i\)), producing sharper concentration with more samples. However, if the per-coordinate sensitivities \(c_i\) do not shrink, the rate may be limited.

4 Examples and canonical applications

4.1 Bounded-difference statistics

A prototypical pattern is \(f\) formed from bounded primitives. For instance, if \(X_i\) take values in an interval and \(f\) is obtained by composing coordinate-wise bounded operations in a way that each coordinate can move the final statistic by at most \(c_i\), McDiarmid yields immediate tail bounds.

Typical examples include:

sums or averages of bounded transforms;
statistics that apply a bounded “clipping” or truncation to each sample;
functions derived from bounded loss functions in learning settings.

4.2 Concentration for empirical averages with bounded effects

Consider \[ f(X)=\frac{1}{n}\sum_{i=1}^n g(X_i), \] where \(g\) is bounded: \(a\le g(\cdot)\le b\). Changing \(X_i\) can change \(f\) by at most \(\frac{b-a}{n}\), so one may take \(c_i=\frac{b-a}{n}\). Then \[

\Pr\left(	f-\mathbb{E}f	\ge t\right)

\le 2\exp\left(-\frac{2n t^2}{(b-a)^2}\right), \] which resembles classical Hoeffding-type concentration, but McDiarmid frames it as a sensitivity argument.

4.3 Functions of independent samples

Beyond averages, many learning and statistics quantities are functions of a sample with bounded sensitivity. Examples include:

empirical risk computed from bounded loss terms (each sample affects the empirical mean only through its own loss contribution);
normalized counts of events where one coordinate can change the count by at most 1 (then normalized by \(n\));
statistics built from limited-impact transformations, such as bounded kernels followed by averaging.

In these cases, the key step is to determine \(c_i\) for the function of the entire sample.

4.4 Concentration for random permutations (via standard reductions)

McDiarmid is stated for independent inputs, but in some problems one may reduce random permutation sampling to a bounded-differences setting by comparing exposures of individual positions under a martingale argument or through couplings. The resulting bounds often have a similar exponential \(t^2\) form. Practically, this is used when an algorithm’s output depends on ordering, and the effect of revealing one element is bounded.

5 Proof sketch and key ideas

5.1 Martingale approach

A common proof strategy constructs a martingale that gradually reveals the random variables \(X_1,\dots,X_n\). The target function value \(f(X_1,\dots,X_n)\) is expressed as the terminal value of this martingale, and the bounded differences condition becomes a bound on each martingale increment.

5.2 Doob martingale construction

Define the filtration \(\mathcal{F}_i=\sigma(X_1,\dots,X_i)\). The Doob martingale is \[ M_i=\mathbb{E}[f(X_1,\dots,X_n)\mid \mathcal{F}_i],\quad i=0,1,\dots,n, \] so \(M_0=\mathbb{E}f\) and \(M_n=f\). The deviation \(f-\mathbb{E}f\) equals \(M_n-M_0\), and the increments \(M_i-M_{i-1}\) measure how much the conditional expectation changes when one additional coordinate is revealed.

5.3 Bounded increments and conditional variance control

Under bounded differences, each increment is controlled: altering \(X_i\) while keeping other coordinates fixed changes \(f\) by at most \(c_i\), which in turn implies \(	M_i-M_{i-1}	\le c_i\). This yields a “bounded increments” martingale condition sufficient for exponential concentration.

5.4 Exponential moment technique

One then studies exponential moments of the martingale increments. A standard step uses inequalities for \(\exp(\lambda Y)\) when \(Y\) is bounded, leading to an upper bound on \(\mathbb{E}[\exp(\lambda(M_n-M_0))]\) in terms of \(\sum_i c_i^2\).

5.5 Deriving the final tail bound

Applying Markov’s inequality to the exponential moment, \[ \Pr(M_n-M_0\ge t) \le \inf_{\lambda>0}\exp(-\lambda t)\,\mathbb{E}[\exp(\lambda(M_n-M_0))], \] and optimizing over \(\lambda\) produces the stated exponent \(-2t^2/\sum_i c_i^2\). A corresponding argument yields the two-sided bound by considering deviations in both directions.

6 Connections and generalizations

6.1 Relation to Azuma–Hoeffding inequality

Azuma–Hoeffding provides concentration for martingales with bounded increments. McDiarmid’s inequality can be viewed as a specialized application: the bounded differences property ensures bounded increments in the Doob martingale associated with \(f(X)\). Thus, McDiarmid is often treated as the “function-of-independent-variables” form of Azuma–Hoeffding.

6.2 Generalizations beyond bounded differences

Several extensions relax strict boundedness:

replacing bounded differences with sub-Gaussian-type sensitivity conditions;
using variance-sensitive bounds where increments are controlled in expectation rather than uniformly;
allowing different moment conditions on the effect of coordinate changes.

These variants aim to maintain concentration when exact boundedness is too restrictive.

6.3 Symmetrization and alternative concentration methods

In statistical learning, symmetrization techniques can compare deviations to those of symmetrized samples (e.g., via Rademacher variables). While McDiarmid focuses on coordinate-wise sensitivity, symmetrization often complements it when one analyzes complexity or uniform deviations over classes of functions.

7 Practical use in statistics and machine learning

7.1 Turning sensitivity bounds into confidence intervals

To use McDiarmid, practitioners:

express the quantity of interest as \(f(X_1,\dots,X_n)\);
verify bounded differences and compute \(c_i\);
choose \(t\) so that the right-hand side equals a target failure probability \(\delta\);
report that with probability at least \(1-\delta\), the statistic lies within \(t\) of its expectation (or sometimes within \(t\) above/below it).

This yields a ready-made high-probability guarantee.

7.2 Bounding deviations of estimators

Many estimators are sample functionals with limited per-sample influence. When the estimator’s sensitivity can be bounded, McDiarmid provides non-asymptotic deviation inequalities. This is common for:

empirical means of bounded losses;
clipped or truncated estimators;
risk estimates where each data point affects the aggregate in a controlled manner.

7.3 Uniform bounds via covering/union strategies

When one needs concentration simultaneously over many choices (e.g., many parameters, hypotheses, or thresholds), one can combine pointwise McDiarmid bounds with:

union bounds over a finite set;
discretization via covering numbers for continuous parameter spaces;
chaining or related refinement techniques.

The output is typically a high-probability uniform deviation bound, though it may weaken as the model class grows.

7.4 Robustness to small perturbations in data

Bounded differences correspond to robustness: if changing one observation cannot strongly perturb the statistic, the inequality implies the statistic remains stable with high probability. This interpretation aligns with general notions of algorithmic stability, particularly in settings where each training point has limited influence on the learned outcome.

8 Limitations and how to check them

8.1 Verifying bounded differences in practice

The main technical burden is establishing constants \(c_i\). Analysts often check:

algebraic dependence on each coordinate (does \(f\) scale like \(1/n\) when changing one point?);
whether discontinuities or non-smooth operations introduce large jumps;
whether boundedness assumptions on inputs or on internal transformations are sufficient to make coordinate effects uniformly bounded.

If \(c_i\) cannot be obtained, the inequality may not be informative.

8.2 Handling unbounded or heavy-tailed inputs

McDiarmid’s classical form requires a uniform bound on how much \(f\) changes when one coordinate changes. With unbounded inputs, \(c_i\) may be infinite unless one introduces truncation/clipping or otherwise bounds the functional’s sensitivity through preprocessing. As a result, many pipelines use robustification strategies to create a bounded-differences structure.

8.3 Dependence violations and what to do next

If inputs are not independent, applying McDiarmid directly can produce incorrect guarantees. Alternatives depend on the dependence model, such as:

martingale concentration tailored to dependent sequences;
mixing-based concentration inequalities;
techniques that exploit exchangeability or other structure, often with modified sensitivity measures.

In practice, one selects a concentration framework consistent with the data-generating mechanism.

9 Variants for different dependence structures (high-level)

9.1 Exchangeable inputs (overview)

Exchangeability replaces independence by symmetry under permutations. For exchangeable arrays, concentration results may still be possible, but they typically require additional structural assumptions or use different martingale/exposure schemes. The constants controlling sensitivity can become more complex because “revealing one coordinate” does not fully decouple the remaining uncertainty.

9.2 Weak dependence and alternative inequalities (overview)

When dependence is mild, weak-dependence inequalities (often expressed via mixing coefficients or coupling arguments) can yield concentration with rates that degrade relative to the independent case. Conceptually, one again seeks a sensitivity-to-increment mapping, but with dependence controlling how much past variables influence future ones.

10 Summary and takeaways

10.1 Checklist for applying McDiarmid’s inequality

Identify the random vector \(X_1,\dots,X_n\) and confirm independence.
Define the statistic as \(f(X_1,\dots,X_n)\) and ensure measurability and finite expectation.
Prove the bounded differences property and compute constants \(c_i\).
Apply the tail bound to obtain probabilities of deviations from \(\mathbb{E}f\).
If needed, extend from pointwise to uniform statements via union/covering strategies.

10.2 Typical workflows for statisticians

A common workflow is to start with the estimator or algorithmic output, then (i) bound the effect of changing one data point, (ii) translate that bound into \(c_i\), (iii) plug into McDiarmid to obtain high-probability inequalities, and (iv) combine these with other analytical steps (e.g., discretization, stability arguments, or risk decomposition). The result is a transparent bridge between bounded sensitivity assumptions and measurable probabilistic guarantees.