Bounded-Difference Inequality for Independent Inputs

Why Coordinatewise Changes Matter

Many statistics are functions of a whole data set, not just sums of independent terms. A statistic can still concentrate if no single observation can change its value very much. The key is to quantify that effect separately for each input. McDiarmid’s inequality turns those coordinatewise limits, together with independence, into a tail bound around the statistic’s expectation.

The inputs themselves must be independent; the output terms or features of the statistic do not need to be independent. This distinction makes the result useful for nonlinear functions, including statistics whose contributions interact.

Definition: Let $E_1,\ldots,E_n$ be measurable spaces, and let $g:E_1\times\cdots\times E_n\to\mathbb{R}$ be measurable. The function $g$ has coordinatewise change limits $c_1,\ldots,c_n$, where each $c_i\geq 0$, if whenever two input vectors differ only in coordinate $i$, $$ |g(x_1,\ldots,x_i,\ldots,x_n)-g(x_1,\ldots,x_i',\ldots,x_n)|\leq c_i. $$

The bound is required for every allowed choice of the other coordinates and every pair of values in coordinate $i$. It therefore controls the largest possible change, not an average change. By changing coordinates one at a time, any two input vectors $x,y$ satisfy

|g(x)-g(y)|\leq \sum_{i=1}^n c_i.

In particular, if $g$ is finite at one input vector, this bound makes it bounded on the product space. For independent inputs $X_1,\ldots,X_n$, we can therefore use the expectation and exponential moments of $g(X_1,\ldots,X_n)$.

McDiarmid’s Inequality

The scale in the bound is the sum of squared coordinatewise limits, $S=\sum_{i=1}^n c_i^2$. Squaring matters: one coordinate with a large possible effect contributes more than several coordinates with small effects.

Theorem (McDiarmid’s inequality): Let $X_1,\ldots,X_n$ be independent random variables taking values in $E_1,\ldots,E_n$, and let $g:E_1\times\cdots\times E_n\to\mathbb{R}$ be measurable with coordinatewise change limits $c_1,\ldots,c_n$. If $S=\sum_{i=1}^n c_i^2>0$, then for every $t>0$, $$ P\bigl(g(X_1,\ldots,X_n)-E[g(X_1,\ldots,X_n)]\geq t\bigr) \leq \exp\left(-\frac{2t^2}{S}\right). $$ The same bound holds for the lower tail: $$ P\bigl(g(X_1,\ldots,X_n)-E[g(X_1,\ldots,X_n)]\leq -t\bigr) \leq \exp\left(-\frac{2t^2}{S}\right). $$ Consequently, the probability that the absolute deviation is at least $t$ is at most $2\exp(-2t^2/S)$. If $S=0$, $g(X_1,\ldots,X_n)$ is constant, so each of these probabilities is zero for $t>0$.

The proof uses Hoeffding’s lemma: if a random variable $Z$ lies almost surely in an interval of length $d$, then, for every real $\lambda$,

E\exp\bigl(\lambda(Z-E[Z])\bigr)\leq \exp\left(\frac{\lambda^2d^2}{8}\right).

We use this established moment bound to prove the needed exponential bound by induction on the number of inputs. The induction integrates one independent input at a time; it does not require $g$ to be additive.

Deriving the Exponential Moment Bound

Write $G=g(X_1,\ldots,X_n)$. The central step is to show that for every real $\lambda$,

E\exp\bigl(\lambda(G-E[G])\bigr) \leq \exp\left(\frac{\lambda^2}{8}\sum_{i=1}^n c_i^2\right).

For $n=1$, this is Hoeffding’s lemma, since $g(X_1)$ lies in an interval of length at most $c_1$. Suppose now that the result holds for $n-1$ inputs. For a fixed value $x_n$, define

m(x_n)=E\bigl[g(X_1,\ldots,X_{n-1},x_n)\bigr],

where the expectation integrates over the first $n-1$ inputs. Measurability and boundedness ensure this function is measurable and the integrals exist. The induction hypothesis, applied with $x_n$ fixed, gives

E\left[\exp\bigl(\lambda(g(X_1,\ldots,X_{n-1},x_n)-m(x_n))\bigr)\right] \leq \exp\left(\frac{\lambda^2}{8}\sum_{i=1}^{n-1}c_i^2\right).

The bound $c_n$ also limits the range of $m$. For any $x_n,x_n'$, integrating the coordinatewise inequality over the first $n-1$ inputs gives $|m(x_n)-m(x_n')|\leq c_n$. Thus $m(X_n)$ lies in an interval of length at most $c_n$. Independence allows us to integrate first over $X_1,\ldots,X_{n-1}$, holding $X_n$ fixed, and then over $X_n$. Using the induction bound and Hoeffding’s lemma yields

\begin{aligned} E\exp\bigl(\lambda(G-E[G])\bigr) &=E\left[\exp\bigl(\lambda(m(X_n)-E[m(X_n)])\bigr) E\left[\exp\bigl(\lambda(G-m(X_n))\bigr)\mid X_n\right]\right]\\ &\leq \exp\left(\frac{\lambda^2}{8}\sum_{i=1}^{n-1}c_i^2\right) E\exp\bigl(\lambda(m(X_n)-E[m(X_n)])\bigr)\\ &\leq \exp\left(\frac{\lambda^2}{8}\sum_{i=1}^{n}c_i^2\right). \end{aligned}

Here $E[m(X_n)]=E[G]$ by integration over the independent inputs. This completes the induction. $\square$

To obtain the upper tail, apply Markov’s inequality to $\exp(\lambda(G-E[G]))$, for $\lambda>0$. The moment bound gives

P(G-E[G]\geq t)\leq \exp\left(-\lambda t+\frac{\lambda^2S}{8}\right).

The exponent is minimized at $\lambda=4t/S$, which gives $\exp(-2t^2/S)$. Applying the same argument to $-G$, whose coordinatewise change limits are also $c_i$, gives the lower-tail bound. The two-sided bound follows by adding the upper- and lower-tail probabilities. If $S=0$, all $c_i$ vanish, and changing coordinates one at a time shows that $g$ is constant. $\square$

Worked Applications

Worked Example: A Mean of Independent Bounded Inputs

Suppose $X_1,\ldots,X_{25}$ are independent Bernoulli random variables, with possibly different success probabilities $p_i$, and let $\bar X=25^{-1}\sum_{i=1}^{25}X_i$. Find a bound on the probability that $\bar X$ exceeds its expectation by at least $0.2$.

Changing $X_i$ from 0 to 1, or from 1 to 0, changes the mean by $1/25$. Thus $c_i=1/25$ for every $i$, and

S=\sum_{i=1}^{25}c_i^2=25\left(\frac{1}{25}\right)^2=\frac{1}{25}.

Since $E[\bar X]=25^{-1}\sum_{i=1}^{25}p_i$, McDiarmid’s inequality gives

P\left(\bar X-E[\bar X]\geq 0.2\right) \leq \exp\left(-\frac{2(0.2)^2}{1/25}\right) =\exp(-2)\approx 0.1353.

No common success probability is needed. Independence and the range of each input are enough for this bound.

Worked Example: An Empirical Distribution Function at One Point

Let $X_1,\ldots,X_{100}$ be independent observations from any distribution, and fix a real number $a$. The empirical distribution function at $a$ is

F_{100}(a)=\frac{1}{100}\sum_{i=1}^{100}\mathbf{1}\{X_i\leq a\}.

Changing one observation changes at most one indicator, so $c_i=1/100$ and $S=100(1/100)^2=1/100$. Also, $E[F_{100}(a)]=P(X_1\leq a)$ when the observations have a common distribution. For an upward deviation of $0.15$,

P\left(F_{100}(a)-P(X_1\leq a)\geq 0.15\right) \leq \exp\left(-\frac{2(0.15)^2}{1/100}\right) =\exp(-4.5)\approx 0.0111.

The same calculation bounds a downward deviation by $0.0111$, so the probability of an absolute deviation of at least $0.15$ is at most $2\exp(-4.5)\approx 0.0222$. This calculation concerns one fixed $a$; it does not by itself bound the largest deviation over all $a$.

Worked Example: A Function With Interacting Inputs

Let $X_1,X_2,X_3$ be independent Bernoulli random variables with success probability $1/2$, and set $g(X_1,X_2,X_3)=X_1X_2+X_2X_3$. Find a bound on $P(g-E[g]\geq 1)$, then compare it with the exact probability.

Changing $X_1$ changes $g$ by at most $X_2\leq 1$, so $c_1=1$. Changing $X_2$ changes $g$ by at most $X_1+X_3\leq 2$, so $c_2=2$. Changing $X_3$ changes $g$ by at most $X_2\leq 1$, so $c_3=1$. Therefore $S=1+4+1=6$.

Each product has expectation $1/4$, since its two Bernoulli inputs are independent. Hence $E[g]=1/4+1/4=1/2$. McDiarmid’s inequality gives

P(g-E[g]\geq 1)\leq \exp\left(-\frac{2}{6}\right) =\exp(-1/3)\approx 0.7165.

For the exact probability, $g-1/2\geq 1$ requires $g\geq 1.5$. The only possible value of $g$ at least $1.5$ is $2$, which occurs only when $X_1=X_2=X_3=1$. Thus the exact probability is $1/8=0.125$, below the valid but loose bound. The example shows that the theorem accommodates interacting terms, while its guarantee can be conservative.

Using the Bound Carefully

The practical work is often in identifying a valid $c_i$. To do so, hold every other input fixed and compare the statistic before and after changing input $i$. The bound must cover the largest such change. Once the limits are established, independence supplies the product structure used in the proof.

Common mistake: assuming the function must be a sum. The theorem applies to measurable functions of independent inputs, including nonlinear functions. The proof does not require a decomposition into independent output terms.
Common mistake: treating a typical change as a maximum change. A small average effect does not establish a coordinatewise limit. The $c_i$ must cover every allowed replacement of that input.
Common mistake: using independence of the output terms. Independence is required of $X_1,\ldots,X_n$. Output terms may share inputs and therefore be dependent.
Common mistake: overlooking a loose bound. A correct sensitivity limit can still produce an uninformative probability bound, as in the interacting-input example. The theorem guarantees validity, not sharpness.

This inequality is useful when a statistic is complicated but its sensitivity to individual observations is easy to control. It provides a concentration guarantee without requiring an exact distribution for the statistic. The sum $\sum_i c_i^2$ also makes the effect of sample size and unequal coordinate sensitivities explicit.

Check Your Understanding

Try these questions using the definition and theorem above.

If changing coordinate $i$ can change $g$ by at most $c_i$, what quantity determines the denominator in McDiarmid’s exponent?
For the average of $n$ independent variables in $[0,1]$, what coordinatewise change limits apply?
Why does the proof need independence of the inputs but not independence of separate terms that make up $g$?
For a lower-tail bound, which function can be substituted into the upper-tail argument?
Explain why a coordinatewise change limit must control the largest possible change rather than the average change.