Local Dependence and Stein Neighborhoods

Why Local Dependence Fits Stein’s Method

A sum can be built from variables that are not independent but whose dependence is confined to small groups. The full sum may be difficult to analyze directly. A useful strategy is to examine one summand at a time and remove the variables that can interact with it.

For a centered sum, this produces a decomposition into a local part and a part independent of the selected summand. Stein’s equation then converts the normal-approximation problem into two kinds of error: fluctuations in a local covariance term, and a remainder controlled by local third moments.

Dependency Neighborhoods

Let $X_1,\dots,X_n$ be square-integrable random variables with $\mathbb E X_i=0$, and let $W=\sum_{i=1}^n X_i$. For each index $i$, choose a set $A_i\subseteq\{1,\dots,n\}$ containing $i$. The set $A_i$ is a dependency neighborhood when $X_i$ is independent of the collection of variables outside $A_i$. Independence here means independence from the random vector formed by all those variables, not just pairwise independence from each one.

Definition: A family $(A_i)_{i=1}^n$ is a family of dependency neighborhoods for $(X_i)_{i=1}^n$ if $i\in A_i$ and $X_i$ is independent of $\sigma(X_j:j\notin A_i)$ for every $i$. Define the neighborhood sum and its complement by $$ V_i=\sum_{j\in A_i}X_j,\qquad W_i=\sum_{j\notin A_i}X_j. $$ Then $W=V_i+W_i$, and $X_i$ is independent of $W_i$.

The neighborhoods need not have the same size, and the sets $A_i$ need not be symmetric in their indices. Their role is to identify, for each summand, a portion of the sum that can be separated from it by independence.

Worked Example: Independent Summands

Suppose $X_1,\dots,X_n$ are mutually independent and centered. Take $A_i=\{i\}$. Then $V_i=X_i$ and $W_i=\sum_{j\ne i}X_j$. Since $X_i$ is independent of the whole vector of the other summands, these are valid dependency neighborhoods. Writing $\sigma^2=\mathbb E W^2$, we have $$ \sigma^2=\sum_{i=1}^n\mathbb E X_i^2. $$ The covariance error that will appear below is zero in this example: $X_iV_i=X_i^2$ is independent of $W_i$, so its covariance with any integrable function of $W_i$ vanishes. Local dependence therefore includes the independent case, while allowing the neighborhoods to be larger.

A Covariance Identity for the Variance

Assume $\sigma^2=\operatorname{Var}(W)>0$. A key identity expresses the variance using only neighborhood variables. Put $c_i=\mathbb E[X_iV_i]$. Since the variables are centered, $\mathbb E W=0$, and therefore $\sigma^2=\mathbb E W^2=\sum_i\mathbb E[X_iW]$. For each $i$, independence of $X_i$ and $W_i$ gives $\mathbb E[X_iW_i]=\mathbb E X_i\,\mathbb E W_i=0$. Thus:

Proposition: For centered square-integrable variables with dependency neighborhoods, $$ \sigma^2=\sum_{i=1}^n c_i =\sum_{i=1}^n\mathbb E[X_iV_i]. $$

Proof. Since $W=\sum_iX_i$, $$ \mathbb E W^2=\sum_{i=1}^n\mathbb E[X_iW]. $$ For each $i$, use $W=V_i+W_i$. Independence and centering imply $$ \mathbb E[X_iW_i]=\mathbb E X_i\,\mathbb E W_i=0, $$ so $\mathbb E[X_iW]=\mathbb E[X_iV_i]$. Summing gives the claimed identity. $\square$

Worked Example: A Moving Sum of Rademacher Variables

Let $Y_1,\dots,Y_{n+1}$ be independent Rademacher variables, each taking the values $1$ and $-1$ with probability $1/2$, and set $X_i=Y_i+Y_{i+1}$ for $1\le i\le n$, where $n\ge2$. Take $A_i=\{j:1\le j\le n,\ |j-i|\le1\}$. The variable $X_i$ uses only $Y_i,Y_{i+1}$. Each $X_j$ outside $A_i$ uses underlying $Y$-variables disjoint from these, so $X_i$ is independent of the entire outside collection.

Each $X_i$ has variance $2$. Adjacent summands have covariance $1$, because they share one Rademacher variable, while summands at distance at least two have covariance $0$. Consequently, $c_i=\mathbb E[X_iV_i]$ is $3$ at each endpoint and $4$ at every interior index. Hence $$ \sum_{i=1}^n c_i=6+4(n-2)=4n-2. $$ Directly, $W=Y_1+2Y_2+\cdots+2Y_n+Y_{n+1}$, so independence of the $Y_j$'s gives $\operatorname{Var}(W)=1+4(n-1)+1=4n-2$, in agreement with the identity.

The Stein Decomposition

Let $Z$ be standard normal. For a suitable test function $h$, the normal Stein equation has the form $g'(x)-xg(x)=h(x)-\mathbb E h(Z)$. Thus the difference between the expectation of $h(W/\sigma)$ and its standard normal counterpart is the expectation of $g'(W/\sigma)-(W/\sigma)g(W/\sigma)$. The next result decomposes exactly this quantity.

Theorem: Suppose $X_1,\dots,X_n$ are centered, square-integrable variables with dependency neighborhoods, and $0<\sigma^2=\operatorname{Var}(W)<\infty$. Let $g$ be twice continuously differentiable with $\|g''\|_\infty<\infty$, and assume the expectations below exist. Then $$ \begin{aligned} &\mathbb E\left[g'\left(\frac W\sigma\right)-\frac W\sigma g\left(\frac W\sigma\right)\right]\\ &=\frac{1}{\sigma^2}\sum_{i=1}^n c_i \left\{\mathbb E g'\left(\frac W\sigma\right) -\mathbb E g'\left(\frac {W_i}\sigma\right)\right\}\\ &\quad-\frac{1}{\sigma^2}\sum_{i=1}^n \operatorname{Cov}\left(X_iV_i,g'\left(\frac {W_i}\sigma\right)\right)-R, \end{aligned} $$ where $c_i=\mathbb E[X_iV_i]$ and the remainder satisfies $$ |R|\le \frac{\|g''\|_\infty}{2\sigma^3} \sum_{i=1}^n\mathbb E\left[|X_i|V_i^2\right]. $$ In particular, the absolute value of the Stein discrepancy is at most $$ \frac{1}{\sigma^2}\sum_{i=1}^n \left|\operatorname{Cov}\left(X_iV_i,g'\left(\frac {W_i}\sigma\right)\right)\right| +\frac{\|g''\|_\infty}{\sigma^3}\sum_{i=1}^n|c_i|\,\mathbb E|V_i| +\frac{\|g''\|_\infty}{2\sigma^3} \sum_{i=1}^n\mathbb E\left[|X_i|V_i^2\right]. $$

Proof. By the covariance identity, $\sum_i c_i=\sigma^2$. Also, $X_i$ is independent of $W_i$ and is centered, so $\mathbb E[X_i g(W_i/\sigma)]=0$. It follows that $$ \mathbb E\left[\frac W\sigma g\left(\frac W\sigma\right)\right] =\frac1\sigma\sum_{i=1}^n \mathbb E\left[X_i\left\{ g\left(\frac{W_i+V_i}{\sigma}\right)-g\left(\frac{W_i}{\sigma}\right) \right\}\right]. $$ Taylor's theorem with a bounded second derivative gives $$ g\left(\frac{W_i+V_i}{\sigma}\right)-g\left(\frac{W_i}{\sigma}\right) =\frac{V_i}{\sigma}g'\left(\frac{W_i}{\sigma}\right)+r_i, \qquad |r_i|\le\frac{\|g''\|_\infty V_i^2}{2\sigma^2}. $$ Therefore the last expectation equals $$ \frac1{\sigma^2}\sum_i\mathbb E\left[X_iV_i g'\left(\frac{W_i}{\sigma}\right)\right]+R, $$ with the stated bound on $R$. For each $i$, expand the expectation as $$ \mathbb E\left[X_iV_i g'\left(\frac{W_i}{\sigma}\right)\right] =c_i\,\mathbb E g'\left(\frac{W_i}{\sigma}\right) +\operatorname{Cov}\left(X_iV_i,g'\left(\frac{W_i}{\sigma}\right)\right). $$ Subtract this expression from $\mathbb E g'(W/\sigma)$, using $\sum_i c_i=\sigma^2$. This proves the decomposition. Finally, the mean value theorem implies $$ \left|\mathbb E g'\left(\frac W\sigma\right) -\mathbb E g'\left(\frac {W_i}\sigma\right)\right| \le\frac{\|g''\|_\infty}{\sigma}\mathbb E|V_i|. $$ Applying this inequality to each term weighted by $|c_i|/\sigma^2$, and using the remainder bound, gives the stated upper bound. $\square$

What the Error Terms Measure

The covariance term records how much the local product $X_iV_i$ still fluctuates with the outside sum $W_i$, as seen through $g'(W_i/\sigma)$. The neighborhood condition makes $X_i$ independent of $W_i$, but it does not generally make $X_iV_i$ independent of $W_i$: the other variables in $V_i$ may themselves be related to variables outside the neighborhood. Dropping this covariance without a further argument is a common mistake.

The Taylor remainder is controlled by $\mathbb E[|X_i|V_i^2]$, a local third-moment quantity. There is also a shift term, bounded by $|c_i|\mathbb E|V_i|$, because the derivative is evaluated at $W_i/\sigma$ rather than $W/\sigma$. If $g$ solves the Stein equation for $h$, the theorem bounds $|\mathbb E h(W/\sigma)-\mathbb E h(Z)|$ by its right-hand side. The derivative bounds for normal Stein solutions can then turn this decomposition into a bound for a chosen class of test functions.

Worked Example: Two Identical Variables in Each Independent Block

Let $Z_1,\dots,Z_m$ be independent Rademacher variables, and define $X_{2k-1}=X_{2k}=Z_k$ for $1\le k\le m$. Choose $A_{2k-1}=A_{2k}=\{2k-1,2k\}$. Each variable is independent of the collection outside its pair. Here $W=2\sum_k Z_k$, so $\sigma^2=4m$. For either index in pair $k$, $V_i=2Z_k$, $W_i=2\sum_{\ell\ne k}Z_\ell$, and $$ c_i=\mathbb E[Z_k(2Z_k)]=2. $$ Thus $\sum_i c_i=4m=\sigma^2$. Moreover, $X_iV_i=2$ is constant, so its covariance with $g'(W_i/\sigma)$ is zero. Each summand in the third-moment sum is $\mathbb E[|X_i|V_i^2]=4$, giving a total of $8m$; likewise $|c_i|\mathbb E|V_i|=4$ for each index, also totaling $8m$. This example shows that neighborhoods can group strongly dependent variables while remaining independent of the outside collection.

Choosing and Checking Neighborhoods

A valid neighborhood is a statement about independence from a whole collection. Pairwise zero covariance with variables outside $A_i$ is not enough. Before applying the decomposition, check the following:

Each neighborhood contains its own index.
The selected variable is independent of the vector of all variables outside its neighborhood.
The sum has positive finite variance, and the local moments in the bound exist.
The variance identity is consistent with a direct variance calculation when one is available.

Smaller neighborhoods can reduce the local-moment terms, but they are useful only if the required independence really holds. Conversely, enlarging a neighborhood preserves the local-versus-outside idea only when the variable remains independent of the entire collection left outside. The decomposition makes this trade-off visible: local size affects the moment sums, while residual dependence appears explicitly in the covariance errors.

Check Your Understanding

Use the definitions and decomposition above to answer these questions.

Why must a dependency neighborhood contain the index of the variable it describes?
Show why $\mathbb E[X_iW_i]=0$ follows from the neighborhood condition and centering.
Why does independence of $X_i$ and $W_i$ not by itself imply that the covariance term in the theorem is zero?
Which term in the bound is controlled directly by the Taylor remainder, and what local moment does it involve?
For independent centered summands with $A_i=\{i\}$, explain why the covariance term vanishes.