Tutorials › Statistical Learning (Graduate) › Bounded Differences and McDiarmid’s Inequality

Home  /  Tutorials  /  Concentration for Learning

Concentration for Learning · Tutorial 113 of 989

Bounded Differences and McDiarmid’s Inequality

Learn to specify bounded-difference constants and use McDiarmid’s inequality to bound deviations of functions of independent inputs.

Beginner 9 min read

What You'll Learn

  • Define coordinate-wise bounded differences on a product of independent inputs.
  • State the one-sided and two-sided forms of McDiarmid’s inequality.
  • Calculate the sensitivity constants and sum of squared constants in examples.
  • Apply the inequality to a bounded average, a sample maximum, and a category count.
  • Recognize common errors involving dependence, scaling, and deviation thresholds.

Why Coordinate Sensitivity Matters

Many statistics are functions of an entire data set, rather than simple averages of individual observations. Examples include a maximum, the number of distinct categories observed, or a complicated score computed from all the inputs. To control the fluctuation of such a statistic, it can be enough to know how much its value could change when one input is replaced while all the others stay fixed.

This idea is useful when the statistic is not itself a sum of independent terms. The inputs can still be independent even when the function of those inputs is complicated. McDiarmid’s inequality turns bounds on one-coordinate changes into a probability bound around the function’s expectation.

Bounded Differences

Definition: Let \(X_1,\ldots,X_n\) be independent random variables taking values in measurable spaces \(\mathcal X_1,\ldots,\mathcal X_n\). Let \(f:\mathcal X_1\times\cdots\times\mathcal X_n\to\mathbb R\) be measurable and integrable. The function \(f\) has bounded differences with constants \(c_1,\ldots,c_n\), where each \(c_i\geq 0\), if for every \(i\), every choice of the other coordinates, and all \(x_i,x_i'\in\mathcal X_i\),

\(|f(x_1,\ldots,x_i,\ldots,x_n)-f(x_1,\ldots,x_i',\ldots,x_n)|\leq c_i.\)

Equivalently, this condition may be imposed on sets of full probability for each input. The constant \(c_i\) bounds the effect of replacing input \(i\), not the size of that input.

Write \(Z=f(X_1,\ldots,X_n)\) and \(C=\sum_{i=1}^n c_i^2\). The relevant scale is \(C\), the sum of the squared coordinate-wise bounds. A coordinate with a larger possible effect contributes more because its bound is squared. If \(C=0\), changing any one coordinate has no effect; by changing coordinates one at a time, \(f\) is constant on the product of the input domains.

Theorem (McDiarmid’s inequality): Suppose \(X_1,\ldots,X_n\) are independent, \(f(X_1,\ldots,X_n)\) is integrable, and \(f\) has bounded differences with constants \(c_1,\ldots,c_n\). If \(C=\sum_{i=1}^n c_i^2>0\), then for every \(t>0\),
$$ P\bigl(f(X_1,\ldots,X_n)-E[f(X_1,\ldots,X_n)]\geq t\bigr) \leq \exp\left(-\frac{2t^2}{C}\right). $$
The corresponding two-sided bound is
$$ P\bigl(|f(X_1,\ldots,X_n)-E[f(X_1,\ldots,X_n)]|\geq t\bigr) \leq 2\exp\left(-\frac{2t^2}{C}\right). $$

The theorem does not require the \(X_i\) to have the same distribution. It does require independence, and the bounded-differences condition must apply regardless of the values of the other coordinates. The quantity \(t\) is the absolute deviation from the expectation, while \(C\) determines how quickly the bound decreases as that deviation grows.

Two Useful Consequences

The coordinate-wise condition also controls the change between any two complete input vectors. This fact helps explain why the individual bounds add along a sequence of replacements.

Proposition: If \(f\) has bounded differences with constants \(c_1,\ldots,c_n\), then for any \(x=(x_1,\ldots,x_n)\) and \(y=(y_1,\ldots,y_n)\),
$$ |f(x)-f(y)|\leq \sum_{i:\,x_i\ne y_i}c_i. $$

Proof. List the coordinates where \(x\) and \(y\) differ as \(i_1,\ldots,i_k\). Form a sequence of vectors starting at \(x\), replacing coordinate \(i_1\) by its value in \(y\), then coordinate \(i_2\), and continuing until the vector is \(y\). Each consecutive pair differs in just one coordinate, so the change in \(f\) at step \(j\) is at most \(c_{i_j}\). The triangle inequality therefore gives

$$ |f(x)-f(y)| \leq \sum_{j=1}^k |f(x^{(j)})-f(x^{(j-1)})| \leq \sum_{j=1}^k c_{i_j} = \sum_{i:\,x_i\ne y_i}c_i. $$

This is a deterministic consequence of the definition; independence is not needed for it. Independence enters McDiarmid’s probability bound.

The two-sided version of the theorem follows directly from its one-sided version and the union bound. Apply the one-sided inequality to \(f\) for the upper tail. For the lower tail, apply it to \(-f\), which has the same coordinate bounds. Then

$$ \begin{aligned} P(|f-E[f]|\geq t) &\leq P(f-E[f]\geq t)+P(-(f-E[f])\geq t)\\ &\leq \exp(-2t^2/C)+\exp(-2t^2/C)\\ &=2\exp(-2t^2/C). \end{aligned} $$

Thus the factor of \(2\) in the two-sided statement comes from combining two one-sided events; it is not part of the exponent.

Worked Applications

Worked Example: A Bounded Average

Let \(X_1,\ldots,X_{25}\) be independent observations in \([0,1]\), not necessarily identically distributed, and let \(f(X_1,\ldots,X_{25})=\frac{1}{25}\sum_{i=1}^{25}X_i\). Find the one-sided McDiarmid bound for an upward deviation of \(t=0.2\).

Replacing \(X_i\) by another value in \([0,1]\) changes the average by at most \(1/25\), since

$$ \left|\frac{1}{25}\sum_{j=1}^{25}X_j-\frac{1}{25}\left(\sum_{j\ne i}X_j+X_i'\right)\right| =\frac{|X_i-X_i'|}{25} \leq \frac{1}{25}. $$

Thus \(c_i=1/25\) for every \(i\), so \(C=25(1/25)^2=1/25=0.04\). Substituting \(t=0.2\) gives

$$ P(f-E[f]\geq 0.2) \leq \exp\left(-\frac{2(0.2)^2}{0.04}\right) =\exp(-2) \approx 0.1353. $$

The two-sided bound is \(2\exp(-2)\approx 0.2707\). The calculation depends on the range of each observation and on the average’s factor \(1/25\); it does not require identical distributions.

Worked Example: The Maximum of Uniform Observations

Let \(X_1,\ldots,X_4\) be independent Uniform\((0,1)\) random variables, and define \(M=\max_i X_i\). Replacing any one coordinate can change the maximum by at most \(1\), so \(c_i=1\) and \(C=4\). First calculate the expectation. For \(0\leq x\leq 1\),

$$ P(M\leq x)=P(X_1\leq x,\ldots,X_4\leq x)=x^4. $$

Therefore \(M\) has density \(4x^3\) on \([0,1]\), and

$$ E[M]=\int_0^1 x(4x^3)\,dx=4\left[\frac{x^5}{5}\right]_0^1=\frac45=0.8. $$

For an upward deviation of \(t=0.15\), McDiarmid’s inequality gives

$$ P(M-E[M]\geq 0.15) \leq \exp\left(-\frac{2(0.15)^2}{4}\right) =\exp(-0.01125) \approx 0.9888. $$

For comparison, the exact probability is \(P(M\geq 0.95)=1-0.95^4=0.18549375\). The general bound is valid but not tight here. A distribution-specific calculation can be much more informative when it is available.

Worked Example: Counting Observed Categories

Suppose six independent observations each fall into one of three categories, with probability \(1/3\) for each category. Let \(K\) be the number of distinct categories observed. Replacing one observation can remove at most one category from the observed set and add at most one. These changes cannot combine to alter the total count by more than one: if the old category disappears, the new category either was already present or replaces it. Hence \(c_i=1\) for all six inputs and \(C=6\).

For each category, the probability it is not observed is \((2/3)^6=64/729\). Its probability of being observed is \(1-64/729=665/729\). Writing \(K\) as the sum of the three indicators that a category appears, linearity of expectation gives

$$ E[K]=3\left(1-\left(\frac23\right)^6\right) =3\left(\frac{665}{729}\right) =\frac{665}{243} \approx 2.7366. $$

For an upward deviation \(t=0.25\), the inequality yields

$$ P(K-E[K]\geq 0.25) \leq \exp\left(-\frac{2(0.25)^2}{6}\right) =\exp\left(-\frac{1}{48}\right) \approx 0.9794. $$

This example illustrates how to handle a statistic that is not an average: identify the effect of a single replacement, then use the resulting constants. As with the maximum, the bound may be conservative.

Common Mistakes and Practical Interpretation

A frequent error is to use the sum of the bounds, \(\sum_i c_i\), in McDiarmid’s exponent. The theorem uses \(\sum_i c_i^2\). The sum \(\sum_i c_i\) instead appears in the deterministic proposition bounding how much \(f\) can change between two vectors. These are different statements with different roles.

Another error is to overlook scaling. If a statistic is an average of \(n\) observations in an interval of length \(b-a\), replacing one observation changes it by at most \((b-a)/n\), not \(b-a\). The corresponding sum of squared bounds is \((b-a)^2/n\). Missing the factor \(1/n\) can make the resulting concentration bound far weaker than the correct one.

Finally, coordinate-wise bounded changes alone do not justify McDiarmid’s inequality when the inputs are dependent. The theorem’s independence assumption is essential. Nor should the bound be mistaken for an exact tail probability: it is a general upper bound around \(E[f]\), and it can be loose, as the maximum example shows. The main practical work is often choosing valid, informative \(c_i\) before substituting into the theorem.

Key takeaway: For independent inputs, bound the change in the statistic caused by replacing each input separately. Square those coordinate bounds, add them, and use McDiarmid’s inequality to control deviations from the statistic’s expectation.

Check Your Understanding

Use the definitions and results above to answer these questions.

  1. For an average of \(n\) independent observations in \([a,b]\), what is a valid bound \(c_i\) for replacing one observation, and what is \(\sum_i c_i^2\)?
  2. Why does the deterministic bound between two input vectors not require independence, while McDiarmid’s inequality does?
  3. If \(C=9\) and \(t=1\), write the one-sided McDiarmid bound and the two-sided bound.
  4. A function changes by at most \(0.1\) when any one of 20 inputs is replaced. What is \(C\)?
  5. Explain why a valid McDiarmid bound can still be uninformative for a particular function and threshold.

Previous

Next

Back to Tutorials
Clinical Biostats