Bounded Differences for Pairwise U-Statistics

Why Pairwise Averages Need a Different Sensitivity Calculation

A sample mean averages one contribution per observation. A pairwise statistic instead averages a kernel over all unordered pairs, so each observation appears in many terms. Those pair terms are generally dependent, even when the original observations are independent. The useful route to concentration is therefore to ask a different question: how much can the whole average change if just one observation is replaced?

For a bounded kernel, the answer is small because only the pairs containing that observation can change. Counting those pairs gives a bounded-difference constant, and McDiarmid’s inequality then controls deviations of the statistic from its expectation. The key is to count affected terms relative to the total number of pairs.

Definition and Sensitivity Bound

Definition: Let $X_1,\ldots,X_n$ be independent random variables with values in a measurable space $\mathcal X$, where $n\geq 2$. Let $h:\mathcal X\times\mathcal X\to\mathbb R$ be a measurable, symmetric kernel, meaning $h(x,y)=h(y,x)$, and suppose $a\leq h(x,y)\leq b$ for all $x,y$. The order-two U-statistic is $$ U_n=\binom{n}{2}^{-1}\sum_{1\leq i<j\leq n}h(X_i,X_j). $$ Its kernel range width is $R=b-a$. When the $X_i$ are identically distributed, $E[U_n]=E[h(X_1,X_2)]$, where $X_1$ and $X_2$ are independent draws from their common distribution.

The definition allows independent observations that are not identically distributed. In that case, the expectation is the average of the pair-specific expectations, rather than one common kernel expectation. The concentration calculation below needs independence and the common kernel range, not identical distributions.

Lemma: If the $i$-th coordinate of the data is replaced while all other coordinates remain fixed, the value of $U_n$ changes by at most $$ c_i=\frac{n-1}{\binom{n}{2}}R=\frac{2R}{n}. $$

To see the count behind the lemma, fix $i$. Exactly $n-1$ unordered pairs contain $i$, one for each other observation. Every other pair is unchanged. For an affected pair, the old and new kernel values both lie in $[a,b]$, so their difference in absolute value is at most $b-a=R$. Thus the absolute change in the unnormalized sum is at most $(n-1)R$. Dividing by the $\binom n2$ terms proves the stated bound.

McDiarmid’s Inequality for the Pairwise Average

McDiarmid’s inequality states that if a measurable function $g(X_1,\ldots,X_n)$ of independent random variables changes by at most $c_i$ when coordinate $i$ alone is replaced, then, for every $t>0$,

P\!\left(g-E[g]\geq t\right)\leq \exp\!\left(-\frac{2t^2}{\sum_{i=1}^n c_i^2}\right).

Applying it to $U_n$ gives a direct concentration guarantee around $E[U_n]$. The next result records both the one-sided and two-sided forms.

Theorem: Under the assumptions in the definition, for every $t>0$, $$ P\!\left(U_n-E[U_n]\geq t\right) \leq \exp\!\left(-\frac{nt^2}{2R^2}\right). $$ Consequently, $$ P\!\left(\lvert U_n-E[U_n]\rvert\geq t\right) \leq 2\exp\!\left(-\frac{nt^2}{2R^2}\right). $$ The two-sided bound may be replaced by its minimum with $1$.

Proof. The sensitivity lemma gives $c_i=2R/n$ for every $i$, so

\sum_{i=1}^n c_i^2 =n\left(\frac{2R}{n}\right)^2 =\frac{4R^2}{n}.

Substituting this sum into McDiarmid’s inequality yields

P\!\left(U_n-E[U_n]\geq t\right) \leq \exp\!\left(-\frac{2t^2}{4R^2/n}\right) =\exp\!\left(-\frac{nt^2}{2R^2}\right).

For the lower tail, apply the same one-sided inequality to $-U_n$; its coordinate sensitivities are also bounded by $c_i$. Thus $P(E[U_n]-U_n\geq t)$ has the same upper bound. The event $\lvert U_n-E[U_n]\rvert\geq t$ is the union of the upper- and lower-tail events, so the union bound gives the factor $2$. Probabilities are at most $1$, which justifies taking the minimum with $1$. $\square$

If the observations are identically distributed, the theorem’s center is the population pairwise quantity $\theta=E[h(X_1,X_2)]$. The result is not restricted to estimating a mean of individual losses: it applies to any measurable symmetric kernel with a finite, uniformly bounded range. Its force comes from the one-coordinate replacement calculation, not from independence among the pair terms.

Worked Applications

Worked Example: Pairwise Disagreement in a Binary Sample

Let $X_1,\ldots,X_4$ be independent Bernoulli random variables with $P(X_i=1)=p$, and let $h(x,y)=\mathbf 1\{x\ne y\}$. This kernel is symmetric and takes values in $[0,1]$, so $R=1$.

For two independent Bernoulli draws, disagreement occurs when the first is $0$ and the second is $1$, or vice versa. Therefore $$ E[h(X_1,X_2)]=(1-p)p+p(1-p)=2p(1-p). $$ Since all six pairs have this same expectation, $E[U_4]=2p(1-p)$.

For the observed sample $(0,0,1,1)$, the six pairs consist of one $0$-versus-$0$ pair, one $1$-versus-$1$ pair, and four disagreeing pairs. Hence $$ U_4=\frac{4}{\binom42}=\frac{4}{6}=\frac23. $$ At $p=1/2$, the expectation is $2(1/2)(1/2)=1/2$, and the observed deviation is $2/3-1/2=1/6$.

The sensitivity bound is $c_i=2R/n=2/4=1/2$, so $\sum_i c_i^2=4(1/2)^2=1$. For $t=1/6$, the one-sided bound is $$ P(U_4-E[U_4]\geq 1/6)\leq \exp\!\left(-\frac{2(1/6)^2}{1}\right) =\exp(-1/18)\approx 0.946. $$ This is a valid but loose upper bound; it is not the probability of observing this particular sample.

Worked Example: Checking the Exponent at a Specified Deviation

Let $n=4$, let $X_i$ be independent Bernoulli$(1/2)$ variables, and use the kernel $h(x,y)=R\mathbf 1\{x\ne y\}$, where $R=\sqrt{2/15}$. Its range is $[0,R]$. The sensitivity of each coordinate is $c_i=2R/4=R/2$, and therefore $$ \sum_{i=1}^4c_i^2=4\left(\frac R2\right)^2=R^2=\frac{2}{15}. $$

At $t=1/3$, the McDiarmid exponent is $$ \frac{2t^2}{\sum_i c_i^2} =\frac{2(1/3)^2}{2/15} =\frac{30(1/3)^2}{2} =\frac{30}{9\cdot 2} =\frac53 \approx 1.667. $$ Thus the upper-tail probability is at most $\exp(-5/3)\approx 0.189$. In particular, the intermediate quantity $30(1/3)^2/2$ is $5/3$, not $5/9$.

This bound remains mathematically valid even though the example’s statistic lies between $0$ and $R$, and its expectation is $R/2$. Its maximum possible absolute deviation is consequently $R/2=\sqrt{2/15}/2\approx 0.183$, which is less than $1/3$; the event in this particular example is actually impossible. That comparison illustrates why a concentration bound need not be sharp.

Worked Example: A Continuous Pairwise Distance

Suppose $X_1,\ldots,X_5$ are independent Uniform$[0,1]$ variables and $h(x,y)=|x-y|$. The kernel is symmetric and lies in $[0,1]$, so $R=1$. Its population expectation is $$ E|X_1-X_2| =2\int_0^1\int_0^y(y-x)\,dx\,dy =2\int_0^1\frac{y^2}{2}\,dy =\frac13. $$ The factor $2$ accounts for the two triangular halves of the unit square; the diagonal has area zero.

For the observed values $0,1/4,1/2,3/4,1$, the ten pairwise distances sum to $$ \frac14+\frac12+\frac34+1 +\frac14+\frac12+\frac34 +\frac14+\frac12+\frac14 =5. $$ Therefore $U_5=5/\binom52=5/10=1/2$, a deviation of $1/2-1/3=1/6$ above its expectation.

Here $c_i=2/5$, so $\sum_i c_i^2=5(2/5)^2=4/5$. The one-sided bound at $t=1/6$ is $$ P(U_5-E[U_5]\geq 1/6) \leq \exp\!\left(-\frac{2(1/6)^2}{4/5}\right) =\exp(-5/72)\approx 0.933. $$ The calculation applies to this specific observed distance statistic because the observations are independent and the kernel is bounded, not because the ten distances are independent.

What the Bound Does and Does Not Say

The exponent improves linearly with $n$ at a fixed deviation $t$, when the kernel range $R$ is held fixed. The mechanism is that one observation affects $n-1$ terms, but the statistic averages over $\binom n2$ terms; its worst-case influence is therefore $2R/n$. Squaring that influence and summing over the $n$ independent coordinates produces a total of $4R^2/n$.

The theorem controls deviations from $E[U_n]$. For identically distributed observations this is $E[h(X_1,X_2)]$, but the theorem alone does not establish that a chosen kernel answers a scientific or learning question of interest. Nor does it use sharper properties such as a small variance or a degenerate kernel. Such refinements require additional assumptions and arguments.

Common Mistake: Treating Pair Terms as Independent

A tempting but invalid argument is to regard the $\binom n2$ terms $h(X_i,X_j)$ as independent and apply an independent-sample bound with sample size $\binom n2$. Terms sharing an observation are generally dependent. For example, $h(X_1,X_2)$ and $h(X_1,X_3)$ both depend on $X_1$, so independence does not follow from independence of the original $X_i$.

The correction is to apply McDiarmid’s inequality to the function of the independent observations $X_1,\ldots,X_n$, not to pretend the pair terms are independent. Compute how replacing each original observation changes the entire average, use $c_i=2R/n$, and then sum the $n$ squared sensitivities. This gives the exponent $nt^2/(2R^2)$, rather than an unjustified exponent based on $\binom n2$ independent terms.

Key takeaway: For a bounded order-two U-statistic, one coordinate changes at most $n-1$ kernel terms. Dividing that total possible change by $\binom n2$ gives sensitivity $2R/n$, which yields McDiarmid concentration around the statistic’s expectation.

Check Your Understanding

Work through these questions by identifying the independent inputs and counting affected pairs.

For a kernel with range $[2,7]$, what is the range width and the coordinate sensitivity when $n=10$?
Why can two terms $h(X_1,X_2)$ and $h(X_1,X_3)$ be dependent even if $X_1,X_2,X_3$ are independent?
For $n=8$ and kernel range width $R=2$, calculate $\sum_i c_i^2$ and the exponent in the one-sided McDiarmid bound.
Which assumption lets $E[U_n]$ be written as $E[h(X_1,X_2)]$ for every pair in the sum?
If a kernel is bounded in $[-3,4]$, what value of $R$ belongs in the concentration bound, and why is it not the upper endpoint alone?