Exchangeable-Pair Bounds for Random Permutation Sums

Why Swapping Positions Helps

A statistic formed by assigning $n$ objects to $n$ positions has dependence built into it: once one assignment is made, the remaining assignments cannot vary independently. A useful way to retain this dependence while gaining a tractable comparison is to make a small random change to the assignment.

For a uniform random permutation, swapping two positions is a natural change. The original and modified statistics have the same distribution, and for a broad class of permutation sums their conditional mean difference is a fixed multiple of the original statistic. This is precisely the structure that lets the exchangeable-pair method produce a normal-approximation bound.

Centered Permutation Sums

Let $n\ge 2$, let $\pi$ be uniform on the permutations of $\{1,\ldots,n\}$, and let $a=(a_{ij})$ be a real $n\times n$ array. We study the permutation sum

W=\sum_{i=1}^n a_{i,\pi(i)}.

The useful case is when the array is centered in both directions. This centering is not a restrictive assumption on the statistic: it can be obtained by subtracting a constant from a sum built from any array.

Definition: The array $a$ is doubly centered if every row sum and every column sum is zero: $$ \sum_{j=1}^n a_{ij}=0\quad\text{for every }i, \qquad \sum_{i=1}^n a_{ij}=0\quad\text{for every }j. $$

Indeed, given any array $b$, write its row means as $r_i=n^{-1}\sum_j b_{ij}$, its column means as $c_j=n^{-1}\sum_i b_{ij}$, and its grand mean as $m=n^{-2}\sum_{i,j}b_{ij}$. The array $a_{ij}=b_{ij}-r_i-c_j+m$ is doubly centered. Also, $\sum_i a_{i,\pi(i)}=\sum_i b_{i,\pi(i)}-\sum_i r_i-\sum_j c_j+nm$, so this operation changes the permutation sum only by a deterministic constant.

Worked Example: Centering a Concrete Array

Take $$ b=\begin{pmatrix}3&0&1\\2&4&0\\1&2&5\end{pmatrix}. $$ Each column has mean $2$, and the row means are $4/3,2,8/3$. The grand mean is $2$, so $a_{ij}=b_{ij}-r_i-c_j+m=b_{ij}-r_i$. Thus $$ a=\begin{pmatrix}5/3&-4/3&-1/3\\0&2&-2\\-5/3&-2/3&7/3\end{pmatrix}. $$ The row sums are $0,0,0$, and the column sums are $5/3+0-5/3=0$, $-4/3+2-2/3=0$, and $-1/3-2+7/3=0$. For every permutation, the centered sum is the original sum minus $4/3+2+8/3=6$. The sum of squared entries is $64/3$, so the variance formula proved below gives variance $32/3$ for this centered sum.

The Swap Pair and Its Regression Identity

Choose an unordered pair of distinct positions uniformly from the $\binom n2$ possibilities, independently of $\pi$. Swap the values of $\pi$ at these positions to obtain $\pi'$, and put $W'=\sum_i a_{i,\pi'(i)}$. Since swapping twice restores the original permutation, the joint distribution of $(\pi,\pi')$, and hence of $(W,W')$, is invariant under exchanging its two coordinates. Such a pair is called exchangeable.

Theorem: If $a$ is doubly centered, the swap pair satisfies $$ \mathbb E[W'-W\mid \pi]=-\frac{2}{n-1}W. $$ Moreover, $$ \mathbb E W=0,\qquad \operatorname{Var}(W)=\frac{1}{n-1}\sum_{i,j=1}^n a_{ij}^2. $$

Proof. Fix $\pi$. Swapping positions $i$ and $j$ changes $W$ by $$ \delta_{ij}=a_{i,\pi(j)}+a_{j,\pi(i)}-a_{i,\pi(i)}-a_{j,\pi(j)}. $$ To sum these changes, first sum over all ordered pairs $i\ne j$. The first term sums to $-W$: for each $i$, the row sum $\sum_j a_{i,\pi(j)}$ is zero, so omitting $j=i$ leaves $-a_{i,\pi(i)}$. The second term also sums to $-W$, by the same reasoning with the roles of $i$ and $j$ exchanged. Each of the last two terms sums to $-(n-1)W$. Therefore $$ \sum_{i\ne j}\delta_{ij}=-2nW. $$ Each unordered pair contributes twice to this sum. Dividing the unordered-pair total, $-nW$, by $\binom n2$ proves the conditional regression identity. For the mean and variance, uniformity gives $\mathbb E W=n^{-1}\sum_{i,j}a_{ij}=0$. Write $B=\sum_{i,j}a_{ij}^2$. The diagonal terms in $\mathbb E W^2$ contribute $B/n$. For $i\ne k$, $$ \sum_{j\ne l}a_{ij}a_{kl} =\left(\sum_j a_{ij}\right)\left(\sum_l a_{kl}\right)-\sum_j a_{ij}a_{kj} =-\sum_j a_{ij}a_{kj}. $$ Summing this over $i\ne k$ gives $B$, because for each column $j$, $$ \sum_{i\ne k}a_{ij}a_{kj} =\left(\sum_i a_{ij}\right)^2-\sum_i a_{ij}^2 =-\sum_i a_{ij}^2. $$ Each off-diagonal pair $(i,k)$ has probability $1/[n(n-1)]$ of receiving a particular pair of distinct values. Thus the off-diagonal contribution to $\mathbb E W^2$ is $B/[n(n-1)]$. Adding the two contributions gives $$ \mathbb E W^2=\frac Bn+\frac{B}{n(n-1)}=\frac{B}{n-1}. $$ Since $\mathbb E W=0$, this is the variance.

$\square$

The regression coefficient is $\lambda=2/(n-1)$, which is positive and does not depend on the realized permutation. The variance identity also identifies exactly when standardization is possible: if $B>0$, then $\sigma^2=\operatorname{Var}(W)=B/(n-1)>0$.

Worked Example: A Rank-One Array on Three Positions

Let $n=3$, $u=v=(-1,0,1)$, and $a_{ij}=u_i v_j$. Both vectors sum to zero, so the array is doubly centered. The statistic is $W=\sum_i u_i v_{\pi(i)}$. Listing its values over the six permutations gives $2,-2,-1,1,1,-1$. Their average is zero, and their squared average is $$ \mathbb E W^2=\frac{4+4+1+1+1+1}{6}=2. $$ The theorem gives the same result: $\sum_{i,j}a_{ij}^2=(\sum_i u_i^2)(\sum_j v_j^2)=2\cdot2=4$, hence $\operatorname{Var}(W)=4/(3-1)=2$. The swap regression coefficient is $2/(3-1)=1$, so $\mathbb E[W'-W\mid\pi]=-W$.

A Wasserstein Bound from the Pair

For real-valued random variables $Y$ and $Z$, their Wasserstein distance is $$ d_{\mathrm W}(Y,Z)=\sup_h\left|\mathbb E h(Y)-\mathbb E h(Z)\right|, $$ where the supremum is over all functions $h:\mathbb R\to\mathbb R$ with Lipschitz constant at most $1$. Let $Z$ be standard normal. The normal Stein equation is $f'(x)-xf(x)=h(x)-\mathbb E h(Z)$. The standard derivative bounds for its solution, used in normal approximation, are $\|f'\|_\infty\le 1$ and $\|f''\|_\infty\le 2$ (with the second derivative understood almost everywhere).

Theorem: Suppose $(X,X')$ is exchangeable, $\mathbb E X=0$, $\mathbb E X^2=1$, and $\mathbb E[X'-X\mid X]=-\lambda X$ for some $\lambda>0$. Then $$ d_{\mathrm W}(X,Z) \le \mathbb E\left|1-\frac{\mathbb E[(X'-X)^2\mid X]}{2\lambda}\right| +\frac{1}{2\lambda}\mathbb E|X'-X|^3. $$

Proof. Set $\Delta=X'-X$. Exchangeability implies $\mathbb E[\Delta(f(X')+f(X))]=0$. The regression condition gives $\mathbb E[\Delta f(X)]=-\lambda\mathbb E[Xf(X)]$. Subtracting these identities yields $$ \mathbb E[Xf(X)]=\frac{1}{2\lambda}\mathbb E\left[\Delta\bigl(f(X')-f(X)\bigr)\right]. $$ Taylor’s formula and the derivative bound on $f''$ give $$ \left|f(X')-f(X)-\Delta f'(X)\right|\le \frac{\|f''\|_\infty}{2}|\Delta|^2. $$ After multiplying by $|\Delta|$ and taking expectations, the error in replacing $\Delta(f(X')-f(X))$ by $\Delta^2 f'(X)$ is at most $\|f''\|_\infty\mathbb E|\Delta|^3/2$. In the Stein equation, this gives $$ \left|\mathbb E[f'(X)-Xf(X)]\right| \le \|f'\|_\infty\mathbb E\left|1-\frac{\mathbb E[\Delta^2\mid X]}{2\lambda}\right| +\frac{\|f''\|_\infty}{4\lambda}\mathbb E|\Delta|^3. $$ Applying the two stated derivative bounds and taking the supremum over the test functions proves the inequality.

$\square$

For the permutation sum, standardize with $X=W/\sigma$, where $\sigma^2=B/(n-1)>0$, and make the same swap to obtain $X'=W'/\sigma$. The regression coefficient remains $\lambda=2/(n-1)$. In terms of the unstandardized statistic, the bound becomes $$ d_{\mathrm W}(W/\sigma,Z) \le \mathbb E\left|1-\frac{(n-1)^2}{4B}\mathbb E[(W'-W)^2\mid\pi]\right| +\frac{n-1}{4\sigma^3}\mathbb E|W'-W|^3. $$ Conditioning on $\pi$ is valid here because $X$ is determined by $\pi$; it can make the conditional-variance error more explicit than conditioning only on $X$.

Worked Example: The Two-Position Case

Take $n=2$ and $$ a=\begin{pmatrix}1&-1\\-1&1\end{pmatrix}. $$ The array is doubly centered, $W$ equals $2$ or $-2$ with equal probabilities, and $\sigma^2=4$. Thus $X=W/2$ is equally likely to be $1$ or $-1$. Swapping the two positions always changes $X$ to $-X$, so $\Delta=-2X$, $\lambda=2$, $\mathbb E[\Delta^2\mid X]=4=2\lambda$, and $\mathbb E|\Delta|^3=8$. The conditional-variance term in the bound is zero, while the jump term is $8/(2\cdot2)=2$. Therefore $d_{\mathrm W}(X,Z)\le2$. This example shows how the two contributions are evaluated, even when a small permutation has a visibly non-normal distribution.

Interpreting and Using the Bound

The first error term measures how far the conditional squared jump is from its target value $2\lambda$. A deterministic conditional variance equal to that target eliminates this term; otherwise, its fluctuations must be controlled. The second term penalizes large jumps. In a useful normal approximation, both errors should be small after the statistic is standardized.

A common pitfall is to check the linear regression identity and then conclude that the statistic is approximately normal. Regression supplies the exchangeable-pair structure, but it does not by itself make either error term small. Another is to standardize $W$ without checking that $B>0$. If $B=0$, all entries are zero, $W$ is identically zero, and there is no variance-one statistic to which the normal bound applies.

The practical workflow is therefore to center the array, compute $B$ and $\sigma^2$, form the swap pair, and then bound its conditional squared jump and third absolute jump. The resulting estimate makes explicit how the combinatorics of the permutation and the scale of individual swaps govern the approximation.

Check Your Understanding

Use the definitions and calculations in this tutorial to answer the following questions.

Why does subtracting row means, column means, and adding back the grand mean leave the permutation sum changed only by a constant?
Where does the factor $2/(n-1)$ in the swap regression identity come from?
For a doubly centered array, what condition ensures that the permutation sum has positive variance?
In the Wasserstein bound, what does the conditional-variance term measure?
Why does verifying linear regression alone not establish a small normal-approximation error?