Coupling Neighborhoods for Dependent Sums

Why Replace a Neighborhood?

For a sum of dependent random variables, the effect of changing one summand may extend to nearby summands. A useful way to control that dependence is to remove an entire neighborhood at once and replace it with an independent copy. The resulting difference measures how much the sum changes under a local resampling.

This construction fits naturally into normal approximation by Stein's method. The replacement makes the modified sum independent of the summand being analyzed, while the size of the replacement difference controls the error in the Taylor expansion.

Setup and Replacement Coupling

Let $X_1,\ldots,X_n$ be centered random variables with finite second moments, and write

S=\sum_{i=1}^n X_i, \qquad \sigma^2=\operatorname{Var}(S)>0, \qquad W=\frac{S}{\sigma}.

For each $i$, choose a set of indices $A_i\subseteq\{1,\ldots,n\}$ containing $i$. We call $A_i$ a dependence neighborhood for $X_i$ if $X_i$ is independent of the vector $(X_j:j\notin A_i)$. Dependence among variables inside $A_i$ is allowed.

On an enlarged probability space, let $(X_j^{(i)}:j\in A_i)$ be a copy of the whole neighborhood vector $(X_j:j\in A_i)$, independent of all the original variables. It is important to copy the vector jointly: if variables within the neighborhood are dependent, their replacement must preserve that joint law. Define

T_i=\sum_{j\in A_i}X_j, \qquad T_i'=\sum_{j\in A_i}X_j^{(i)}, \qquad W_i^* = W-\frac{T_i-T_i'}{\sigma}.

The sum $W_i^*$ retains the original variables outside $A_i$ and uses an independent copy inside $A_i$. Since $X_i$ is independent of the original variables outside $A_i$, and the copy is independent of the original vector, $W_i^*$ is independent of $X_i$. Also, $\mathbb E T_i'=0$, because every $X_j$ is centered.

Definition: The weighted squared replacement cost is $$ B=\sum_{i=1}^n \mathbb E\!\left[|X_i|\,|T_i-T_i'|^2\right]. $$ It records the squared change caused by replacing the neighborhood, weighted by the size of the summand whose Stein identity is being used.

A Wasserstein Bound from Replacement Costs

For probability laws on the real line with finite first moments, their $1$-Wasserstein distance can be defined by

d_W(U,Z)= \sup_{\substack{h:\mathbb R\to\mathbb R\\ |h(x)-h(y)|\le |x-y|}} \left|\mathbb E h(U)-\mathbb E h(Z)\right|,

where $Z$ has the standard normal distribution. The Lipschitz condition ensures that the expectations are well defined when $U$ has a finite first moment.

Theorem: Suppose the $X_i$ are centered, have finite second moments, and have dependence neighborhoods $A_i$ as defined above. If $\sigma^2=\operatorname{Var}(S)>0$ and $B<\infty$, then $$ d_W(W,Z)\le \frac{3B}{\sigma^3}. $$

Proof. First, independence outside $A_i$ and centering imply $\mathbb E[X_iX_j]=0$ whenever $j\notin A_i$. Consequently, $$ \sum_{i=1}^n\mathbb E[X_i(T_i-T_i')] = \sum_{i=1}^n\sum_{j\in A_i}\mathbb E[X_iX_j] = \sum_{i=1}^n\sum_{j=1}^n\mathbb E[X_iX_j] = \operatorname{Var}(S) = \sigma^2. $$ Here $\mathbb E[X_iT_i']=0$, since $T_i'$ is independent of the centered variable $X_i$. Take a $1$-Lipschitz test function $h$, and let $f$ solve the normal Stein equation $$ f'(x)-xf(x)=h(x)-\mathbb E h(Z). $$ The standard derivative bound for the normal Stein equation gives a solution with $\|f''\|_\infty\le 2$, first for smooth $h$; general Lipschitz $h$ follow by smooth approximation. Thus $$ \left|\mathbb E h(W)-\mathbb E h(Z)\right| = \left|\mathbb E[f'(W)-Wf(W)]\right|. $$ Set $D_i=T_i-T_i'$, so $W-W_i^*=D_i/\sigma$. Independence of $W_i^*$ and $X_i$, together with $\mathbb E X_i=0$, gives $\mathbb E[X_if(W_i^*)]=0$. Taylor's theorem, with the bound on $f''$, yields $$ f(W)-f(W_i^*)= \frac{D_i}{\sigma}f'(W_i^*)+R_i, \qquad |R_i|\le \frac{\|f''\|_\infty}{2}\frac{|D_i|^2}{\sigma^2}. $$ Since $W=S/\sigma$, it follows that $$ \mathbb E[Wf(W)] = \frac{1}{\sigma^2}\sum_{i=1}^n\mathbb E[X_iD_i f'(W_i^*)] +\frac{1}{\sigma}\sum_{i=1}^n\mathbb E[X_iR_i]. $$ Use $\sum_i\mathbb E[X_iD_i]=\sigma^2$ to compare the first term with $\mathbb E f'(W)$. The mean value bound $\left|f'(W_i^*)-f'(W)\right|\le\|f''\|_\infty |D_i|/\sigma$ gives $$ \left| \frac{1}{\sigma^2}\sum_i\mathbb E[X_iD_i f'(W_i^*)] -\mathbb E f'(W) \right| \le \frac{\|f''\|_\infty}{\sigma^3} \sum_i\mathbb E[|X_i||D_i|^2]. $$ The Taylor remainders contribute at most $$ \left|\frac{1}{\sigma}\sum_i\mathbb E[X_iR_i]\right| \le \frac{\|f''\|_\infty}{2\sigma^3} \sum_i\mathbb E[|X_i||D_i|^2]. $$ Combining these estimates and using $\|f''\|_\infty\le2$ gives $$ \left|\mathbb E h(W)-\mathbb E h(Z)\right| \le \frac{3}{\sigma^3}\sum_i\mathbb E[|X_i||D_i|^2] =\frac{3B}{\sigma^3}. $$ Taking the supremum over $h$ proves the result. $\square$

Worked Examples

Worked Example: Independent Rademacher Summands

Let $X_1,\ldots,X_n$ be independent, with $\mathbb P(X_i=1)=\mathbb P(X_i=-1)=1/2$. Take $A_i=\{i\}$. Then $\sigma^2=n$, $T_i=X_i$, and $T_i'=X_i'$, where $X_i'$ is an independent Rademacher copy. Since $|X_i|=1$, and $X_i-X_i'$ is zero with probability $1/2$ and has absolute value $2$ with probability $1/2$, $$ \mathbb E[|X_i||T_i-T_i'|^2] =\mathbb E[(X_i-X_i')^2] =\frac12(0)^2+\frac12(2)^2=2. $$ Thus $B=2n$, and the theorem gives $$ d_W\!\left(\frac{S}{\sqrt n},Z\right) \le \frac{6n}{n^{3/2}} =\frac{6}{\sqrt n}. $$ The bound has the expected order $n^{-1/2}$.

Worked Example: Identical Variables in Independent Pairs

Let $m\ge1$, let $Z_1,\ldots,Z_m$ be independent Rademacher variables, and set $X_{2k-1}=X_{2k}=Z_k$ for $1\le k\le m$. For either index in pair $k$, take $A_i=\{2k-1,2k\}$. The neighborhood sum is $T_i=2Z_k$; its independent copy is $T_i'=2Z_k'$. The total sum is $S=2\sum_{k=1}^m Z_k$, so $\sigma^2=4m$. For each of the $2m$ indices, $$ \mathbb E[|X_i||T_i-T_i'|^2] =4\mathbb E[(Z_k-Z_k')^2] =4\left(\frac12(0)^2+\frac12(2)^2\right) =8. $$ Therefore $B=16m$, and $$ d_W(W,Z)\le\frac{3(16m)}{(4m)^{3/2}} =\frac{6}{\sqrt m}. $$ The neighborhood replacement correctly resamples both copies of $Z_k$ together. Replacing the two variables separately would not preserve their perfect dependence.

Worked Example: A Short-Range Dependent Sum

Let $Z_1,\ldots,Z_{n+1}$ be independent Rademacher variables and define $X_i=Z_i+Z_{i+1}$, for $1\le i\le n$. Choose $$ A_i=\{j:1\le j\le n,\ |j-i|\le1\}. $$ If $j\notin A_i$, $X_j$ uses neither $Z_i$ nor $Z_{i+1}$; hence $X_i$ is independent of the vector of all such $X_j$. Also, $$ S=Z_1+2\sum_{k=2}^{n}Z_k+Z_{n+1}, \qquad \sigma^2=1+4(n-1)+1=4n-2. $$ Every $X_i$ satisfies $|X_i|\le2$, and $A_i$ contains at most three indices, each with $|X_j|\le2$. Thus $|T_i|\le6$. The copied neighborhood has the same bound, so $|T_i-T_i'|\le12$. It follows that each replacement cost is at most $2\cdot12^2=288$, and $B\le288n$. Therefore $$ d_W(W,Z)\le\frac{864n}{(4n-2)^{3/2}}. $$ This estimate is deliberately coarse, but it verifies how a local dependence structure gives a finite replacement-cost bound.

Moment Conditions and Interpretation

The theorem is useful when the neighborhood replacement costs can be estimated directly or controlled by simpler moments. For example, from $|T_i-T_i'|^2\le2|T_i|^2+2|T_i'|^2$ and independence of $X_i$ and $T_i'$, $$ \mathbb E[|X_i||T_i-T_i'|^2] \le 2\mathbb E[|X_i||T_i|^2] + 2\mathbb E|X_i|\,\mathbb E[T_i^2]. $$ Thus finite third moments of the summands are sufficient for finiteness of these costs when each neighborhood is finite: the first term can be bounded by expanding $T_i^2$ and applying Hölder's inequality to each product. In applications, sharper estimates may use cancellations or the actual conditional distribution of $T_i$ given $X_i$, rather than bounding every term by its absolute maximum.

One common pitfall is to make the replacement variables independent one at a time when the neighborhood itself contains dependence. That can change the joint distribution of the neighborhood and invalidate the intended coupling. Another is to omit the variance identity: the leading Taylor term matches $\mathbb E f'(W)$ because the sum of neighborhood covariances is exactly $\sigma^2$. The independence-outside-neighborhood condition and the fact that every $A_i$ contains $i$ ensure this identity.

Takeaway: A valid neighborhood coupling removes the original neighborhood and inserts an independent copy with the same joint law. The aggregate covariance identity supplies the Stein normalization, and the weighted squared replacement costs control the remaining error.

Check Your Understanding

Use the definitions and proof to check how the coupling and its cost work.

Why must the copied neighborhood vector preserve the joint law of the original neighborhood?
Show that $\mathbb E[X_iT_i']=0$ under the stated assumptions.
Where does the identity $\sum_i\mathbb E[X_i(T_i-T_i')]=\sigma^2$ enter the proof?
If $|T_i|\le a_i$ and $|T_i'|\le a_i$ almost surely, give an upper bound for the $i$th replacement cost in terms of $a_i$ and $\mathbb E|X_i|$.
For what reason does replacing neighborhood variables separately risk producing an invalid coupling?