McDiarmid's inequality

In probability theory and theoretical computer science, McDiarmid's inequality (named after Colin McDiarmid ) is a concentration inequality which bounds the deviation between the sampled value and the expected value of certain functions when they are evaluated on independent random variables. McDiarmid's inequality applies to functions that satisfy a bounded differences property, meaning that replacing a single argument to the function while leaving all other arguments unchanged cannot cause too large of a change in the value of the function.

Statement

A function $f:{{𝒳}}_1\times {{𝒳}}_2\times \cdots \times {{𝒳}}_n\to \mathbb{ℝ}$ satisfies the bounded differences property if substituting the value of the $i$th coordinate $x_i$ changes the value of $f$ by at most $c_i$. More formally, if there are constants $c_1,c_2,\dots ,c_n$ such that for all $i\in [n]$, and all $x_1\in {{𝒳}}_1,x_2\in {{𝒳}}_2,\dots ,x_n\in {{𝒳}}_n$,

$\underset{{x_i}^{\prime }\in {{𝒳}}_i}{\sup }|f(x_1,\dots ,x_{i-1},x_i,x_{i+1},\dots ,x_n)-f(x_1,\dots ,x_{i-1},{x_i}^{\prime },x_{i+1},\dots ,x_n)|\le c_i.$

McDiarmid's Inequality — Let $f:{{𝒳}}_1\times {{𝒳}}_2\times \cdots \times {{𝒳}}_n\to \mathbb{ℝ}$ satisfy the bounded differences property with bounds $c_1,c_2,\dots ,c_n$. Consider independent random variables $X_1,X_2,\dots ,X_n$ where $X_i\in {{𝒳}}_i$ for all $i$. Then, for any $\epsilon >0$,

$\text{P}(f(X_1,X_2,\dots ,X_n)-\mathbb{𝔼}[f(X_1,X_2,\dots ,X_n)]\ge \epsilon )\le \exp (-\frac{2{\epsilon }^2}{\sum _{i=1}^n{c}_i^2}),$

$\text{P}(f(X_1,X_2,\dots ,X_n)-\mathbb{𝔼}[f(X_1,X_2,\dots ,X_n)]\le -\epsilon )\le \exp (-\frac{2{\epsilon }^2}{\sum _{i=1}^n{c}_i^2}),$

and as an immediate consequence,

$\text{P}(|f(X_1,X_2,\dots ,X_n)-\mathbb{𝔼}[f(X_1,X_2,\dots ,X_n)]|\ge \epsilon )\le 2\exp (-\frac{2{\epsilon }^2}{\sum _{i=1}^n{c}_i^2}).$

Extensions

Unbalanced distributions

A stronger bound may be given when the arguments to the function are sampled from unbalanced distributions, such that resampling a single argument rarely causes a large change to the function value.

McDiarmid's Inequality (unbalanced) — Let $f:{{𝒳}}^n\to \mathbb{ℝ}$ satisfy the bounded differences property with bounds $c_1,c_2,\dots ,c_n$. Consider independent random variables $X_1,X_2,\dots ,X_n\in {𝒳}$ drawn from a distribution where there is a particular value ${\chi }_0\in {𝒳}$ which occurs with probability $1-p$. Then, for any $\epsilon >0$,

$\text{P}(|f(X_1,\dots ,X_n)-\mathbb{𝔼}[f(X_1,\dots ,X_n)]|\ge \epsilon )\le 2\exp \left(\frac{-{\epsilon }^2}{2p(2-p)\sum _{i=1}^n{c}_i^2+\frac{2}{3}\epsilon \underset{i}{\max }{c}_i}\right).$

This may be used to characterize, for example, the value of a function on graphs when evaluated on sparse random graphs and hypergraphs, since in a sparse random graph, it is much more likely for any particular edge to be missing than to be present.

Differences bounded with high probability

McDiarmid's inequality may be extended to the case where the function being analyzed does not strictly satisfy the bounded differences property, but large differences remain very rare.

McDiarmid's Inequality (Differences bounded with high probability) — Let $f:{{𝒳}}_1\times {{𝒳}}_2\times \cdots \times {{𝒳}}_n\to \mathbb{ℝ}$ be a function and ${𝒴}\subseteq {{𝒳}}_1\times {{𝒳}}_2\times \cdots \times {{𝒳}}_n$ be a subset of its domain and let $c_1,c_2,\dots ,c_n\ge 0$ be constants such that for all pairs $(x_1,\dots ,x_n)\in {𝒴}$ and $(x{\text{'}}_1,\dots ,x{\text{'}}_n)\in {𝒴}$,

$|f(x_1,\dots ,x_n)-f(x{\text{'}}_1,\dots ,x{\text{'}}_n)|\le \sum _{i:x_i\ne x{\text{'}}_i}{c}_i.$

Consider independent random variables $X_1,X_2,\dots ,X_n$ where $X_i\in {{𝒳}}_i$ for all $i$. Let $p=1-\mathrm{P}((X_1,\dots ,X_n)\in {𝒴})$ and let $m=\mathbb{𝔼}[f(X_1,\dots ,X_n)\mid (X_1,\dots ,X_n)\in {𝒴}]$. Then, for any $\epsilon >0$,

$\text{P}(f(X_1,\dots ,X_n)-m\ge \epsilon )\le p+\exp (-\frac{2\max {(0,\epsilon -p\sum _{i=1}^n{c}_i)}^2}{\sum _{i=1}^n{c}_i^2}),$

and as an immediate consequence,

$\text{P}(|f(X_1,\dots ,X_n)-m|\ge \epsilon )\le 2p+2\exp (-\frac{2\max {(0,\epsilon -p\sum _{i=1}^n{c}_i)}^2}{\sum _{i=1}^n{c}_i^2}).$

There exist stronger refinements to this analysis in some distribution-dependent scenarios, such as those that arise in learning theory.

Sub-Gaussian and sub-exponential norms

Let the $k$th centered conditional version of a function $f$ be

$f_k(X)(x):=f(x_1,\dots ,x_{k-1},X_k,x_{k+1},\dots ,x_n)-{\mathbb{𝔼}}_{X{\text{'}}_k}f(x_1,\dots ,x_{k-1},X{\text{'}}_k,x_{k+1},\dots ,x_n),$

so that $f_k(X)$ is a random variable depending on random values of $x_1,\dots ,x_{k-1},x_{k+1},\dots ,x_n$.

McDiarmid's Inequality (Sub-Gaussian norm) — Let $f:{{𝒳}}_1\times {{𝒳}}_2\times \cdots \times {{𝒳}}_n\to \mathbb{ℝ}$ be a function. Consider independent random variables $X=(X_1,X_2,\dots ,X_n)$ where $X_i\in {{𝒳}}_i$ for all $i$. Let $f_k(X)$ refer to the $k$th centered conditional version of $f$. Let $\Vert \cdot {\Vert }_{{\psi }_2}$ denote the sub-Gaussian norm of a random variable. Then, for any $\epsilon >0$,

$\text{P}(f(X_1,\dots ,X_n)-m\ge \epsilon )\le \exp \left(\frac{-{\epsilon }^2}{32e{\Vert \sum _{k\in [n]}\Vert f_k(X){\Vert }_{{\psi }_2}^2\Vert }_{\mathrm{\infty }}}\right).$

McDiarmid's Inequality (Sub-exponential norm) — Let $f:{{𝒳}}_1\times {{𝒳}}_2\times \cdots \times {{𝒳}}_n\to \mathbb{ℝ}$ be a function. Consider independent random variables $X=(X_1,X_2,\dots ,X_n)$ where $X_i\in {{𝒳}}_i$ for all $i$. Let $f_k(X)$ refer to the $k$th centered conditional version of $f$. Let $\Vert \cdot {\Vert }_{{\psi }_1}$ denote the sub-exponential norm of a random variable. Then, for any $\epsilon >0$,

$\text{P}(f(X_1,\dots ,X_n)-m\ge \epsilon )\le \exp \left(\frac{-{\epsilon }^2}{4e^2{\Vert \sum _{k\in [n]}\Vert f_k(X){\Vert }_{{\psi }_1}^2\Vert }_{\mathrm{\infty }}+2\epsilon e\underset{k\in [n]}{\max }{\Vert \Vert f_k(X){\Vert }_{{\psi }_1}\Vert }_{\mathrm{\infty }}}\right).$

Bennett and Bernstein forms

Refinements to McDiarmid's inequality in the style of Bennett's inequality and Bernstein inequalities are made possible by defining a variance term for each function argument. Let

$\begin{array}{rl}B& :=\underset{k\in [n]}{\max }\underset{x_1,\dots ,x_{k-1},x_{k+1},\dots ,x_n}{\sup }|f(x_1,\dots ,x_{k-1},X_k,x_{k+1},\dots ,x_n)-{\mathbb{𝔼}}_{X_k}f(x_1,\dots ,x_{k-1},X_k,x_{k+1},\dots ,x_n)|,\\ V_k& :=\underset{x_1,\dots ,x_{k-1},x_{k+1},\dots ,x_n}{\sup }{\mathbb{𝔼}}_{X_k}{(f(x_1,\dots ,x_{k-1},X_k,x_{k+1},\dots ,x_n)-{\mathbb{𝔼}}_{X_k}f(x_1,\dots ,x_{k-1},X_k,x_{k+1},\dots ,x_n))}^2,\\ {\tilde{\sigma }}^2& :=\sum _{k=1}^n{V}_k.\end{array}$

McDiarmid's Inequality (Bennett form) — Let $f:{{𝒳}}^n\to \mathbb{ℝ}$ satisfy the bounded differences property with bounds $c_1,c_2,\dots ,c_n$. Consider independent random variables $X_1,X_2,\dots ,X_n$ where $X_i\in {{𝒳}}_i$ for all $i$. Let $B$ and ${\tilde{\sigma }}^2$ be defined as at the beginning of this section. Then, for any $\epsilon >0$,

$\text{P}(f(X_1,\dots ,X_n)-\mathbb{𝔼}[f(X_1,\dots ,X_n)]\ge \epsilon )\le \exp (-\frac{\epsilon }{2B}\log (1+\frac{B\epsilon }{{\tilde{\sigma }}^2})).$

McDiarmid's Inequality (Bernstein form) — Let $f:{{𝒳}}^n\to \mathbb{ℝ}$ satisfy the bounded differences property with bounds $c_1,c_2,\dots ,c_n$. Let $B$ and ${\tilde{\sigma }}^2$ be defined as at the beginning of this section. Then, for any $\epsilon >0$,

$\text{P}(f(X_1,\dots ,X_n)-\mathbb{𝔼}[f(X_1,\dots ,X_n)]\ge \epsilon )\le \exp (-\frac{{\epsilon }^2}{2({\tilde{\sigma }}^2+\frac{B\epsilon }{3})}).$

Proof

The following proof of McDiarmid's inequality constructs the Doob martingale tracking the conditional expected value of the function as more and more of its arguments are sampled and conditioned on, and then applies a martingale concentration inequality (Azuma's inequality). An alternate argument avoiding the use of martingales also exists, taking advantage of the independence of the function arguments to provide a Chernoff-bound-like argument. For better readability, we will introduce a notational shorthand: $z_{i\rightharpoondown j}$ will denote $z_i,\dots ,z_j$ for any $z\in {{𝒳}}^n$ and integers $1\le i\le j\le n$, so that, for example,

$f(X_{1\rightharpoondown (i-1)},y,x_{(i+1)\rightharpoondown n}):=f(X_1,\dots ,X_{i-1},y,x_{i+1},\dots ,x_n).$

Pick any ${x_1}^{\prime },{x_2}^{\prime },\dots ,{x_n}^{\prime }$. Then, for any $x_1,x_2,\dots ,x_n$, by triangle inequality,

$\begin{array}{rl}& |f(x_{1\rightharpoondown n})-f(x{\text{'}}_{1\rightharpoondown n})|\\ \le & |f(x_{1\rightharpoondown n})-f(x{\text{'}}_{1\rightharpoondown (n-1)},x_n)|+c_n\\ \le & |f(x_{1\rightharpoondown n})-f(x{\text{'}}_{1\rightharpoondown (n-2)},x_{(n-1)\rightharpoondown n})|+c_{n-1}+c_n\\ \le & \dots \\ \le & \sum _{i=1}^n{c}_i,\end{array}$

and thus $f$ is bounded. Since $f$ is bounded, define the Doob martingale $\{Z_i\}$ (each $Z_i$ being a random variable depending on the random values of $X_1,\dots ,X_i$) as

$Z_i:=\mathbb{𝔼}[f(X_{1\rightharpoondown n})\mid X_{1\rightharpoondown i}]$

for all $i\ge 1$ and $Z_0:=\mathbb{𝔼}[f(X_{1\rightharpoondown n})]$, so that $Z_n=f(X_{1\rightharpoondown n})$. Now define the random variables for each $i$

$\begin{array}{rl}{U}_i& :=\underset{x\in {{𝒳}}_i}{\sup }\mathbb{𝔼}[f(X_{1\rightharpoondown (i-1)},x,X_{(i+1)\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)},X_i=x]-\mathbb{[}f(X_{1\rightharpoondown (i-1)},X_{i\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)}],\\ L_i& :=\underset{x\in {{𝒳}}_i}{\inf }\mathbb{𝔼}[f(X_{1\rightharpoondown (i-1)},x,X_{(i+1)\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)},X_i=x]-\mathbb{[}f(X_{1\rightharpoondown (i-1)},X_{i\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)}].\\ \end{array}$

Since $X_i,\dots ,X_n$ are independent of each other, conditioning on $X_i=x$ does not affect the probabilities of the other variables, so these are equal to the expressions

$\begin{array}{rl}{U}_i& =\underset{x\in {{𝒳}}_i}{\sup }\mathbb{𝔼}[f(X_{1\rightharpoondown (i-1)},x,X_{(i+1)\rightharpoondown n})-f(X_{1\rightharpoondown (i-1)},X_{i\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)}],\\ L_i& =\underset{x\in {{𝒳}}_i}{\inf }\mathbb{𝔼}[f(X_{1\rightharpoondown (i-1)},x,X_{(i+1)\rightharpoondown n})-f(X_{1\rightharpoondown (i-1)},X_{i\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)}].\\ \end{array}$

Note that $L_i\le Z_i-Z_{i-1}\le U_i$. In addition,

$\begin{array}{rl}{U}_i-L_i& =\underset{u\in {{𝒳}}_i,\ell \in {{𝒳}}_i}{\sup }\mathbb{𝔼}[f(X_{1\rightharpoondown (i-1)},u,X_{(i+1)\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)}]-\mathbb{𝔼}[f(X_{1\rightharpoondown (i-1)},\ell ,X_{(i+1)\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)}]\\ & =\underset{u\in {{𝒳}}_i,\ell \in {{𝒳}}_i}{\sup }\mathbb{𝔼}[f(X_{1\rightharpoondown (i-1)},u,X_{(i+1)\rightharpoondown n})-f(X_{1\rightharpoondown (i-1)},l,X_{(i+1)\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)}]\\ & \le \underset{x_u\in {{𝒳}}_i,x_l\in {{𝒳}}_i}{\sup }\mathbb{𝔼}[c_i\mid X_{1\rightharpoondown (i-1)}]\\ & \le c_i\end{array}$

Then, applying the general form of Azuma's inequality to $\left\{Z_i\right\}$, we have

$\text{P}(f(X_1,\dots ,X_n)-\mathbb{𝔼}[f(X_1,\dots ,X_n)]\ge \epsilon )=\mathrm{P}(Z_n-Z_0\ge \epsilon )\le \exp (-\frac{2{\epsilon }^2}{\sum _{i=1}^n{c}_i^2}).$

The one-sided bound in the other direction is obtained by applying Azuma's inequality to $\{-Z_i\}$ and the two-sided bound follows from a union bound. $◻$

See also

• Catalog of articles in probability theory
• Concentration inequality
• Expected value and Variance
• Glossary of probability and statistics
• List of probability topics
• Notation in probability