Coupling and Stein Methods · Tutorial 916 of 946

Normal Approximation with Dependency Graphs

Learn a proved normal-approximation bound for sums with a dependency graph, and see how its error depends on local graph structure and third moments.

Advanced 11 min read

What You'll Learn

Define a dependency graph and the closed and second neighborhoods used in the bound
State the Wasserstein normal-approximation bound and its variance assumption
Follow a proof that controls Taylor remainders and dependence errors
Convert the neighborhood bound into a maximum-degree and third-moment estimate
Apply the estimate to independent variables, a matching, and a path

Why a Graph Can Control Normal Approximation

A sum can contain many dependent terms without being globally dependent in an unstructured way. A graph records which pairs of terms may interact: if two groups of vertices have no edges between them, the corresponding groups of random variables are independent. This local structure can make a sum close to normal even when its summands are not mutually independent.

The bound below is for Wasserstein distance. Its proof has to account for more than the immediate neighbors of each summand: a neighbor may itself be dependent on variables outside the original neighborhood. We therefore track both a closed neighborhood and the vertices within graph distance two.

Dependency Graphs and Neighborhoods

Definition: Let \(Y_1,\ldots,Y_n\) be random variables. A simple graph \(G\) with vertex set \(\{1,\ldots,n\}\) is a dependency graph for these variables if, whenever \(A\) and \(B\) are disjoint vertex sets with no edge joining a vertex of \(A\) to a vertex of \(B\), the random vectors \((Y_i)_{i\in A}\) and \((Y_j)_{j\in B}\) are independent.

Write \(N(i)\) for the set of vertices adjacent to \(i\), and define the closed neighborhood \(B_i=\{i\}\cup N(i)\). Let \(C_i\) be the set of vertices at graph distance at most two from \(i\), including \(i\); vertices in other connected components have infinite distance. Put \(b_i=|B_i|\) and \(c_i=|C_i|\).

Two independence facts will be used in the proof. First, \(Y_i\) is independent of the collection of variables indexed outside \(B_i\): there are no edges from \(i\) to those vertices. Second, the whole vector indexed by \(B_i\) is independent of the vector indexed outside \(C_i\): an edge from \(B_i\) to outside \(C_i\) would give a path of length at most two from \(i\) to that outside vertex.

The second fact is important. A closed neighborhood need not be independent of the variables outside that same neighborhood. Neighbors of \(i\) can have edges to vertices at distance two from \(i\).

Definition: For random variables \(U\) and \(V\) with finite first moments, their Wasserstein distance is \(d_W(U,V)=\sup_h |\mathbb E h(U)-\mathbb E h(V)|\), where the supremum is over all functions \(h:\mathbb R\to\mathbb R\) with Lipschitz constant at most one.

A Normal-Approximation Bound

Let \(Z\) have the standard normal distribution. Suppose \(\mathbb E Y_i=0\) and \(\mathbb E|Y_i|^3<\infty\) for every \(i\). Set \(S=\sum_{i=1}^nY_i\) and \(\sigma^2=\operatorname{Var}(S)\), and assume \(\sigma^2>0\). For each \(i\), define \(m_i=\mathbb E|Y_i|^3\). The following neighborhood sums retain the moments of the individual variables rather than replacing them by a single uniform bound:

Q_B=\sum_{i=1}^n\sum_{j,k\in B_i} (m_i m_j m_k)^{1/3}, \qquad Q_C=\sum_{i=1}^n\sum_{j\in B_i}\sum_{k\in C_i} (m_i m_j m_k)^{1/3}.

Theorem: Under these assumptions,

d_W\!\left(\frac{S}{\sigma},Z\right) \leq \frac{4}{\sigma^3}(Q_B+Q_C).

Thus both the local number of terms and their third absolute moments matter. The second-neighborhood term allows the proof to control dependencies between a summand's neighbors and the rest of the sum.

Proof Using the Normal Stein Equation

Proof. Let \(W=S/\sigma\). For a 1-Lipschitz test function \(h\), the normal Stein equation has a solution \(f\) satisfying \(f'(x)-xf(x)=h(x)-\mathbb E h(Z)\), with \(\|f''\|_\infty\leq 2\). The derivative bound is the standard normal Stein solution bound for Wasserstein test functions; nonsmooth \(h\) can be handled by smooth approximation. It is enough to bound the absolute value of \(\mathbb E[f'(W)-Wf(W)]\). For each \(i\), put \(V_i=\sum_{\ell\notin B_i}Y_\ell\), and \(R_i=\sum_{j\in B_i}Y_j\), so \(S=V_i+R_i\). Since \(Y_i\) is centered and independent of \(V_i\), \(\mathbb E[Y_i f(V_i/\sigma)]=0\). Taylor's theorem, with \(\|f''\|_\infty\leq 2\), gives

\left| \mathbb E[Y_i f(W)] -\frac{1}{\sigma}\sum_{j\in B_i} \mathbb E[Y_iY_j f'(V_i/\sigma)] \right| \leq \frac{1}{\sigma^2} \mathbb E\!\left[|Y_i| \left(\sum_{j\in B_i}|Y_j|\right)^2\right].

Indeed, the Taylor remainder is bounded pointwise by \(\|f''\|_\infty |R_i|^2/(2\sigma^2)\), and \(|R_i|\leq\sum_{j\in B_i}|Y_j|\). Multiplication by \(|Y_i|\) and expectation yield the displayed inequality.

If \(j\notin B_i\), then \(Y_i\) and \(Y_j\) are independent, so \(\mathbb E[Y_iY_j]=0\). Consequently, \(\sigma^2=\sum_i\sum_{j\in B_i}\mathbb E[Y_iY_j]\). Combining this identity with the Taylor estimate and \(W=S/\sigma\), the Stein discrepancy is bounded by a remainder plus the difference between the following two sums:

\frac{1}{\sigma^2}\sum_i\sum_{j\in B_i} \mathbb E[Y_iY_j]\,\mathbb E f'(W) \quad\text{and}\quad \frac{1}{\sigma^2}\sum_i\sum_{j\in B_i} \mathbb E[Y_iY_j f'(V_i/\sigma)].

For the remainder, its contribution to the discrepancy is at most \(\sigma^{-3}\sum_i\mathbb E[|Y_i|(\sum_{j\in B_i}|Y_j|)^2]\). To control the difference of sums, fix \(i\) and \(j\in B_i\), and write \(A=Y_iY_j\) and \(T_i=\sum_{\ell\notin C_i}Y_\ell\). The vector indexed by \(B_i\) is independent of \(T_i\), so \(A\) is independent of \(T_i\). Also, \(|S-T_i|\leq\sum_{k\in C_i}|Y_k|\) and \(|S-V_i|\leq\sum_{k\in B_i}|Y_k|\).

Set \(L=\|f''\|_\infty\leq 2\). The Lipschitz property of \(f'\) gives

\left|\mathbb E[A f'(W)]-\mathbb E[A]\,\mathbb E f'(W)\right| \leq \frac{L}{\sigma}\left\{ \mathbb E\!\left[|A|\sum_{k\in C_i}|Y_k|\right] +\mathbb E|A|\,\mathbb E\!\left[\sum_{k\in C_i}|Y_k|\right] \right\}.

To see this, subtract \(f'(T_i/\sigma)\) in each expectation. Independence makes \(\mathbb E[A f'(T_i/\sigma)]=\mathbb E[A]\mathbb E f'(T_i/\sigma)\); each of the two remaining differences is bounded by \(L|S-T_i|/\sigma\). The other needed comparison is

\left|\mathbb E[A\{f'(W)-f'(V_i/\sigma)\}]\right| \leq \frac{L}{\sigma} \mathbb E\!\left[|A|\sum_{k\in B_i}|Y_k|\right].

Adding these inequalities for \(i\) and \(j\in B_i\), and adding the Taylor remainder, bounds the Stein discrepancy by

\frac{L}{\sigma^3} \left[ \frac12\sum_i\mathbb E\!\left\{|Y_i| \left(\sum_{j\in B_i}|Y_j|\right)^2\right\} +\sum_i\sum_{j\in B_i}\mathbb E\!\left\{|Y_iY_j| \sum_{k\in B_i}|Y_k|\right\} +\sum_i\sum_{j\in B_i}\left\{ \mathbb E\!\left[|Y_iY_j|\sum_{k\in C_i}|Y_k|\right] +\mathbb E|Y_iY_j|\,\mathbb E\!\left[\sum_{k\in C_i}|Y_k|\right] \right\} \right].

For any three indices \(i,j,k\), Hölder's inequality gives \(\mathbb E|Y_iY_jY_k|\leq(m_i m_j m_k)^{1/3}\). Also, \(\mathbb E|Y_iY_j|\leq(m_i m_j)^{1/3}\) and \(\mathbb E|Y_k|\leq m_k^{1/3}\), so \(\mathbb E|Y_iY_j|\,\mathbb E|Y_k|\leq(m_i m_j m_k)^{1/3}\). Expanding the sums inside the expectations therefore bounds the bracket by \(\tfrac32 Q_B+2Q_C\). Since \(L\leq2\), the discrepancy is at most \(\sigma^{-3}(3Q_B+4Q_C)\), which is no greater than \(4\sigma^{-3}(Q_B+Q_C)\). Taking the supremum over the test functions proves the theorem. \(\square\)

A Maximum-Degree Version

A simpler, coarser form uses only the maximum degree \(\Delta=\max_i |N(i)|\) and the total third moment \(M_3=\sum_i m_i\). Then \(b_i\leq b=\Delta+1\) and \(c_i\leq c=1+\Delta^2\): there are at most \(\Delta\) vertices at distance one and \(\Delta(\Delta-1)\) at distance two.

Corollary: With the assumptions of the theorem,

d_W\!\left(\frac{S}{\sigma},Z\right) \leq \frac{4\bigl((\Delta+1)^2+(\Delta+1)(1+\Delta^2)\bigr)}{\sigma^3} \sum_{i=1}^n\mathbb E|Y_i|^3.

For verification, use \((m_i m_j m_k)^{1/3}\leq(m_i+m_j+m_k)/3\). In \(Q_B\), each \(m_i\), \(m_j\), or \(m_k\) is counted at most \(b^2\) times, giving \(Q_B\leq b^2M_3\). In \(Q_C\), each is counted at most \(bc\) times, giving \(Q_C\leq bcM_3\). Substitution into the theorem proves the claim.

Worked Examples

Worked Example: Independent Rademacher Summands

Let \(Y_1,\ldots,Y_n\) be independent, with each taking values \(1\) and \(-1\) with probability \(1/2\). The graph with no edges is a dependency graph, so \(\Delta=0\), \(\sigma^2=n\), and \(M_3=n\). The maximum-degree bound yields

d_W\!\left(\frac{S}{\sqrt n},Z\right) \leq \frac{4(1+1)n}{n^{3/2}} =\frac{8}{\sqrt n}.

This is a valid, though not sharp, quantitative normal-approximation estimate. Its \(n^{-1/2}\) rate comes from the third-moment sum growing linearly in \(n\), while the variance to the power \(3/2\) grows as \(n^{3/2}\).

Worked Example: A Matching Dependency Graph

Let \(n=2m\), and let \(U_1,\ldots,U_m\) be independent Rademacher variables. Set \(Y_{2\ell-1}=Y_{2\ell}=U_\ell\). A matching joining each such pair is a dependency graph: different pairs are independent. Here \(\Delta=1\), \(\sigma^2=\operatorname{Var}(2\sum_{\ell=1}^m U_\ell)=4m\), and \(M_3=2m\). Therefore,

d_W\!\left(\frac{S}{2\sqrt m},Z\right) \leq \frac{4(2^2+2\cdot2)(2m)}{(4m)^{3/2}} =\frac{64m}{8m^{3/2}} =\frac{8}{\sqrt m}.

The bound reflects the fact that each summand has only one neighbor, even though variables within a matched pair are identical.

Worked Example: A Sum with a Path Dependency Graph

Let \(U_1,\ldots,U_{n+1}\) be independent Rademacher variables and set \(Y_i=U_i+U_{i+1}\) for \(1\leq i\leq n\). The path on \(1,\ldots,n\) is a dependency graph: whenever two sets of indices have no edge between them, their underlying sets of \(U\)'s are disjoint, so the corresponding vectors are independent. Each \(Y_i\) has mean zero and variance \(2\); neighboring terms have covariance \(1\), and non-neighbors have covariance zero. Hence

\sigma^2=2n+2(n-1)=4n-2.

Each \(Y_i\) is \(2\) or \(-2\) with total probability \(1/2\), and is zero otherwise. Thus \(m_i=\mathbb E|Y_i|^3=8(1/2)=4\), so \(M_3=4n\). The maximum degree is at most \(2\), giving

d_W\!\left(\frac{S}{\sqrt{4n-2}},Z\right) \leq \frac{4(3^2+3\cdot5)(4n)}{(4n-2)^{3/2}} = \frac{384n}{(4n-2)^{3/2}}.

The factor \(5\) bounds the size of a path vertex's distance-two neighborhood. The estimate is coarse, but it exhibits explicitly how graph degree and third moments enter.

What the Bound Captures—and What It Does Not

A dependency graph describes independence between separated groups, not merely pairwise correlations. A zero covariance between two variables does not, by itself, establish the independence required by the definition. When applying the theorem, verify the graph property for arbitrary separated vertex sets.

The maximum-degree estimate can also be quite conservative: it replaces the detailed neighborhood sums by worst-case sizes. When degrees or moments vary substantially, the theorem's \(Q_B+Q_C\) form can be appreciably more informative. In either form, the variance condition \(\sigma^2>0\) is essential because the approximation concerns the standardized sum \(S/\sigma\).

Check Your Understanding

Use the definitions and proof to check how the graph structure enters the estimate.

Why is \(Y_i\) independent of the sum over vertices outside \(B_i\)?
Why can the vector indexed by \(B_i\) be dependent on variables at distance two from \(i\)?
Where does the variance identity \(\sigma^2=\sum_i\sum_{j\in B_i}\mathbb E[Y_iY_j]\) enter the proof?
For a graph of maximum degree \(\Delta\), why is \(|C_i|\leq1+\Delta^2\)?
What additional assumption, beyond centering and finite third moments, is required to standardize the sum?

Back to Tutorials