CLT under Local Dependence: When Observations Are Connected

June 2, 2026

On this page

When observations share random inputs, the variance of their sum includes covariances between them. We study when dividing the centered sum by its standard deviation gives an approximately standard normal distribution. A dependency graph specifies which groups of observations must be independent. Under this condition, a bound from Stein's method gives sufficient conditions for a central limit theorem (CLT). We then compare it with a bound that directly controls the difference between distribution functions.

The starting result is Ross’s Theorem 3.5. We give the probabilistic argument in full under an explicit dependency-graph assumption. The later Chen–Shao theorem is stated with its conditions and applied to the same example; its longer concentration-inequality proof is not reproduced here.

1. The sum and its dependency graph

Let $(X_1,\ldots,X_n)\sim P_n$ be a real random vector with $\mathbb E_{P_n}X_i=0$ and finite fourth moments. The observations may be dependent, so $P_n$ need not be a product of their marginal distributions. Throughout the graph proof, unmarked $\mathbb E$ , $\operatorname{Var}$ , $\operatorname{Cov}$ , and $\mathbb P$ use this joint distribution or its relevant marginal. The graph is fixed; we do not average over randomly generated graphs. Define

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

A deterministic undirected graph $G$ on $\{1,\ldots,n\}$ is a dependency graph if, for any disjoint vertex sets $I,J$ with no edge between them,

(X_i)_{i\in I}\ \perp\!\!\!\perp\ (X_j)_{j\in J}.

This is independence of two random vectors, not merely pairwise independence. For example, if $U,V$ are independent random signs, then $U,V,UV$ are pairwise independent, but

U\cdot V\cdot(UV)=1\quad\text{almost surely}.

The empty graph is therefore not a dependency graph for this triple.

Write

N_i=\{i\}\cup\{j:\{i,j\}\text{ is an edge of }G\},\qquad D=\max_i|N_i|.

Thus $D$ counts the vertex itself; it is one plus the maximum graph degree. Because the graph is undirected, $j\in N_i$ if and only if $i\in N_j$ . Nonneighbors are independent, so

\begin{aligned} \sigma^2 &=\sum_{i=1}^n\sum_{j=1}^n\mathbb E[X_iX_j]\\ &=\sum_{i=1}^n\sum_{j\in N_i}\mathbb E[X_iX_j]. \end{aligned}

Thus normalization must include covariances between distinct neighboring observations, even when each observation depends on only a small neighborhood.

Constructing the graph from independent inputs

Suppose $\{\varepsilon_v:v\in\mathcal V\}$ are mutually independent, and each observation has the form

X_i=g_i\bigl((\varepsilon_v)_{v\in B_i}\bigr),\qquad B_i\subseteq\mathcal V.

Joining $i$ and $j$ whenever $B_i\cap B_j\ne\varnothing$ gives a dependency graph: two groups with no connecting edge are functions of disjoint sets of independent inputs.

For example, when $B_i$ is the closed one-hop neighborhood of $i$ in an underlying network, the dependency graph may require edges between vertices at network distance two. If the underlying maximum degree is $d$ , then

D\le1+d+d(d-1)=1+d^2.

This construction requires the independent-input representation. A social or spatial network by itself does not establish the required independence.

2. Why the normal distribution leads to Stein’s equation

Let $Z\sim N(0,1)$ , with density $\varphi(x)=(2\pi)^{-1/2}e^{-x^2/2}$ and distribution function $\Phi$ . Expressions $\mathbb E h(Z)$ integrate only $Z\sim N(0,1)$ ; expressions $\mathbb E h(W)$ integrate $W=\sum_iX_i/\sigma$ under $P_n$ . The comparison requires no joint coupling of $W$ and $Z$ . Since $\varphi'(x)=-x\varphi(x)$ , integration by parts gives, for a bounded continuously differentiable $f$ with bounded derivative,

\begin{aligned} \mathbb E f'(Z) &=\int_{\mathbb R}f'(x)\varphi(x)\,dx\\ &=[f(x)\varphi(x)]_{-\infty}^{\infty} -\int_{\mathbb R}f(x)\varphi'(x)\,dx\\ &=\mathbb E[Zf(Z)]. \end{aligned}

To compare $W$ with $Z$ , take a test function $h:\mathbb R\to\mathbb R$ and solve

f_h'(w)-wf_h(w)=h(w)-\mathbb E h(Z).

Multiplication by $e^{-w^2/2}$ yields an integrating factor:

\begin{aligned} \frac{d}{dw}\{e^{-w^2/2}f_h(w)\} &=e^{-w^2/2}\{h(w)-\mathbb E h(Z)\},\\ f_h(w) &=e^{w^2/2}\int_{-\infty}^w e^{-t^2/2}\{h(t)-\mathbb E h(Z)\}\,dt. \end{aligned}

Consequently,

\mathbb E h(W)-\mathbb E h(Z) =\mathbb E\{f_h'(W)-Wf_h(W)\}.

We first use the Wasserstein distance

d_{\mathrm W}(W,Z) =\sup_{\operatorname{Lip}(h)\le1} \left|\mathbb E h(W)-\mathbb E h(Z)\right|,

where $\operatorname{Lip}(h)\le1$ means $|h(x)-h(y)|\le|x-y|$ for every $x,y$ . These expectations exist because $W$ and $Z$ have finite first moments.

To use this distance, we need bounds on the solution of Stein's equation. The following Stein-factor lemma supplies them: for such $h$ , the bounded solution satisfies

\|f_h'\|_\infty\le\sqrt{\frac2\pi},\qquad \operatorname{Lip}(f_h')\le2.

For smooth $h$ , the second inequality can be written $\|f_h''\|_\infty\le2$ ; the Lipschitz formulation also covers nonsmooth $h$ . We use these bounds from Ross, Lemma 2.5. They control the Taylor remainder below, leaving us to bound moments of local sums and count which products can be dependent.

3. A dependency-graph normal-approximation theorem

Theorem 1. Under the centering, fourth-moment, positive-variance, and dependency-graph assumptions above,

\boxed{ \begin{aligned} d_{\mathrm W}(W,Z) &\le \frac{D^2}{\sigma^3}\sum_{i=1}^n\mathbb E|X_i|^3\\ &\quad+\sqrt{\frac{26}{\pi}}\, \frac{D^{3/2}}{\sigma^2} \left(\sum_{i=1}^n\mathbb E X_i^4\right)^{1/2}. \end{aligned}}

This is the bound in Ross, Theorem 3.5, used here with the full graph-independence condition. The proof separates two errors: a Taylor remainder and the fluctuation of a local quadratic sum. No identical-distribution assumption is needed.

Removing the neighborhood creates independence

First, define

\xi_i=\frac{X_i}{\sigma},\qquad \eta_i=\sum_{j\in N_i}\xi_j,\qquad W_i=W-\eta_i=\sum_{j\notin N_i}\xi_j.

The graph condition gives $\xi_i\perp\!\!\!\perp W_i$ . Centering then implies

\mathbb E[\xi_i f_h(W_i)] =\mathbb E\xi_i\,\mathbb E f_h(W_i)=0,

and hence

\mathbb E[Wf_h(W)] =\sum_i\mathbb E\left[\xi_i\{f_h(W)-f_h(W_i)\}\right].

Next, expand around $W$ . The fundamental theorem of calculus and the Lipschitz bound on $f_h'$ give

\begin{aligned} r_i &=f_h(W)-f_h(W-\eta_i)-\eta_i f_h'(W)\\ &=\int_0^{\eta_i}\{f_h'(W-t)-f_h'(W)\}\,dt,\\ |r_i|&\le\int_0^{|\eta_i|}2t\,dt=\eta_i^2. \end{aligned}

Define the normalized local quadratic sum

V=\sum_i\xi_i\eta_i =\frac{1}{\sigma^2}\sum_i\sum_{j\in N_i}X_iX_j.

The variance identity in Section 1 gives $\mathbb E V=1$ . Substituting the expansion into the Stein discrepancy therefore yields

\begin{aligned} \mathbb E\{f_h'(W)-Wf_h(W)\} &=\mathbb E\{f_h'(W)(1-V)\} -\sum_i\mathbb E(\xi_i r_i),\\ \left|\mathbb E\{f_h'(W)-Wf_h(W)\}\right| &\le\sqrt{\frac2\pi}\,\mathbb E|1-V| +\sum_i\mathbb E(|\xi_i|\eta_i^2)\\ &\le\sqrt{\frac2\pi}\sqrt{\operatorname{Var}(V)} +\sum_i\mathbb E(|\xi_i|\eta_i^2). \end{aligned}

The final inequality is Cauchy–Schwarz, using $\mathbb E(1-V)=0$ . Taking the supremum over $h$ proves the intermediate bound

\boxed{ d_{\mathrm W}(W,Z) \le\sqrt{\frac2\pi}\sqrt{\operatorname{Var}(V)} +\sum_i\mathbb E(|\xi_i|\eta_i^2). }

This intermediate bound retains the individual neighborhoods and covariances. When they are known, evaluating it directly can avoid replacing every local contribution by a worst-case maximum-degree bound.

Bounding the Taylor remainder

Expanding the neighborhood square and applying the triangle inequality gives

\sum_i\mathbb E(|\xi_i|\eta_i^2) \le\frac1{\sigma^3}\sum_i\sum_{j,k\in N_i} \mathbb E|X_iX_jX_k|.

By the arithmetic–geometric mean inequality,

|X_iX_jX_k| \le\frac{|X_i|^3+|X_j|^3+|X_k|^3}{3}.

To count each contribution, write $a_i=\mathbb E|X_i|^3$ . There are at most $D^2$ choices of $(j,k)$ for a fixed $i$ , while symmetry of the neighborhoods gives

\begin{aligned} \sum_i\sum_{j,k\in N_i}a_i&\le D^2\sum_i a_i,\\ \sum_i\sum_{j,k\in N_i}a_j &=\sum_j a_j\sum_{i:j\in N_i}|N_i| \le D^2\sum_j a_j. \end{aligned}

The same count applies to $a_k$ . It follows that

\sum_i\mathbb E(|\xi_i|\eta_i^2) \le\frac{D^2}{\sigma^3}\sum_i\mathbb E|X_i|^3.

Bounding the local quadratic fluctuation

For the other term, put

T=\sum_i\sum_{j\in N_i}X_iX_j, \qquad V=T/\sigma^2.

Bilinearity of covariance gives

\operatorname{Var}(T) =\sum_i\sum_{j\in N_i}\sum_k\sum_{\ell\in N_k} \operatorname{Cov}(X_iX_j,X_kX_\ell).

If $\{i,j\}$ and $\{k,\ell\}$ are disjoint and no graph edge connects them, the corresponding products are independent and their covariance vanishes. Thus a potentially nonzero term must satisfy

k\in N_i\cup N_j \quad\text{or}\quad \ell\in N_i\cup N_j.

Let $\mathcal Q$ be the set of ordered quadruples satisfying $j\in N_i$ , $\ell\in N_k$ , and this last condition. For each fixed $(i,j)$ , the first alternative allows at most $2D\cdot D$ pairs $(k,\ell)$ . The second allows at most another $2D\cdot D$ , since $\ell\in N_k$ is equivalent to $k\in N_\ell$ . Consequently,

\#\{(j,k,\ell):(i,j,k,\ell)\in\mathcal Q\} \le D\cdot4D^2=4D^3.

The same bound holds with any one of the four positions fixed: $\mathcal Q$ is invariant under interchanging the members of either pair and under interchanging the two pairs.

Write $m_i=\mathbb E X_i^4$ . Cauchy–Schwarz, followed by Hölder and the arithmetic–geometric mean inequality, gives

\begin{aligned} |\operatorname{Cov}(X_iX_j,X_kX_\ell)| &\le\sqrt{\operatorname{Var}(X_iX_j) \operatorname{Var}(X_kX_\ell)}\\ &\le\sqrt{\mathbb E(X_i^2X_j^2) \mathbb E(X_k^2X_\ell^2)}\\ &\le(m_im_jm_km_\ell)^{1/4}\\ &\le\tfrac14(m_i+m_j+m_k+m_\ell). \end{aligned}

Finally, summing these bounds and using the fixed-position count yields

\begin{aligned} \operatorname{Var}(T) &\le\frac14\sum_{(i,j,k,\ell)\in\mathcal Q} (m_i+m_j+m_k+m_\ell)\\ &\le4D^3\sum_i m_i \le13D^3\sum_i m_i,\\ \sqrt{\frac2\pi}\sqrt{\operatorname{Var}(V)} &\le\sqrt{\frac{26}{\pi}}\, \frac{D^{3/2}}{\sigma^2}\left(\sum_i m_i\right)^{1/2}. \end{aligned}

Combining the two error bounds proves Theorem 1. The direct covariance count under our full graph assumption actually permits $\sqrt{8/\pi}$ in place of $\sqrt{26/\pi}$ ; we retained the latter to display the source theorem's constant. Neither constant is asserted optimal.

4. When does the bound imply a CLT?

For a triangular array $\{X_{ni}:1\le i\le n\}$ , let $D_n$ , $\sigma_n$ , and $W_n$ denote the corresponding quantities. Theorem 1 gives

\begin{gathered} \frac{D_n^2}{\sigma_n^3}\sum_i\mathbb E|X_{ni}|^3\longrightarrow0,\\ \frac{D_n^{3/2}}{\sigma_n^2} \left(\sum_i\mathbb E X_{ni}^4\right)^{1/2}\longrightarrow0 \end{gathered} \quad\Longrightarrow\quad W_n\Rightarrow N(0,1).

For a simple sufficient condition, assume uniformly bounded third and fourth moments and $\sigma_n^2\ge cn$ for some fixed $c>0$ . Then

d_{\mathrm W}(W_n,Z) \le C\left(\frac{D_n^2}{\sqrt n} +\frac{D_n^{3/2}}{\sqrt n}\right),

where $C$ depends only on the moment bounds and $c$ . In particular,

D_n=o(n^{1/4})\quad\Longrightarrow\quad W_n\Rightarrow N(0,1).

This is a sufficient condition from this bound, not a necessary degree threshold. The variance assumption must be verified separately; local dependence allows negative as well as positive covariances.

Example: Overlapping observations on a path

Let $\varepsilon_1,\ldots,\varepsilon_{n+1}$ be independent random signs, each taking $-1$ and $1$ with equal probability, and set

X_i=\varepsilon_i+\varepsilon_{i+1},\qquad 1\le i\le n.

Only adjacent observations share an input. The path graph is a dependency graph, with $D\le3$ . Direct calculation gives

\begin{aligned} \operatorname{Var}(X_i)&=2,\\ \operatorname{Cov}(X_i,X_{i+1})&=1,\\ \operatorname{Cov}(X_i,X_j)&=0\quad(|i-j|>1),\\ \sigma^2&=2n+2(n-1)=4n-2. \end{aligned}

Because $X_i$ equals $-2,0,2$ with probabilities $1/4,1/2,1/4$ ,

\mathbb E|X_i|^3=4,\qquad \mathbb E X_i^4=8.

Thus Theorem 1 implies the explicit bound

d_{\mathrm W}\left(\frac{S}{\sqrt{4n-2}},Z\right) \le\frac{36n}{(4n-2)^{3/2}} +\sqrt{\frac{26}{\pi}}\, \frac{3^{3/2}\sqrt{8n}}{4n-2} =O(n^{-1/2}).

The normalization can also be checked by collecting the independent inputs:

S=\varepsilon_1+2\sum_{i=2}^n\varepsilon_i+\varepsilon_{n+1}.

Ignoring the adjacent covariances would give variance $2n$ . By Slutsky's theorem, the resulting incorrectly normalized sum instead satisfies

\frac{S}{\sqrt{2n}} =\sqrt{\frac{4n-2}{2n}}\,W_n \Rightarrow N(0,2),

not a standard normal limit.

The sign of the shared input also matters. Replacing $X_i$ by $\varepsilon_i-\varepsilon_{i+1}$ preserves the path dependency graph, but telescoping gives

S=\varepsilon_1-\varepsilon_{n+1},\qquad \sigma^2=2,\qquad \mathbb P(S/\sigma=0)=\tfrac12.

This standardized distribution is the same for every $n$ and is not normal. Bounded neighborhoods and bounded observations alone therefore do not suffice.

Example: Growing neighborhoods can still permit a CLT

Partition $n=m_nb_n$ observations into $m_n$ independent blocks, each of size $b_n$ . Within block $r$ , set every observation equal to a single random sign $\varepsilon_r$ . A union of cliques is a dependency graph, and

D_n=b_n,\qquad S_n=b_n\sum_{r=1}^{m_n}\varepsilon_r,\qquad \sigma_n^2=m_nb_n^2=nb_n.

All third absolute and fourth moments equal one. Substitution, without imposing $\sigma_n^2\asymp n$ , gives

\begin{aligned} \frac{D_n^2n}{\sigma_n^3} &=\frac1{\sqrt{m_n}},\\ \frac{D_n^{3/2}\sqrt n}{\sigma_n^2} &=\frac1{\sqrt{m_n}}. \end{aligned}

Therefore $m_n\to\infty$ suffices, even when $b_n$ grows faster than $n^{1/4}$ . Indeed,

W_n=\frac1{\sqrt{m_n}}\sum_{r=1}^{m_n}\varepsilon_r.

At the opposite extreme, one block gives $W_n=\varepsilon_1$ for every $n$ . Increasing the number of copies of the same observation does not create a normal limit.

5. From smooth test functions to distribution functions

For distribution-function error, define the Kolmogorov distance

d_{\mathrm K}(W,Z) =\sup_{z\in\mathbb R}|\mathbb P(W\le z)-\Phi(z)|.

The Wasserstein bound already implies convergence in this metric. To see this directly, let $h_{z,\delta}$ equal one on $(-\infty,z]$ , decline linearly to zero on $[z,z+\delta]$ , and equal zero afterward. Its Lipschitz constant is $1/\delta$ . Since $\varphi\le M=(2\pi)^{-1/2}$ ,

\begin{aligned} \mathbb P(W\le z)-\Phi(z) &\le\mathbb E h_{z,\delta}(W)-\mathbb E h_{z,\delta}(Z)\\ &\quad+\mathbb E h_{z,\delta}(Z)-\Phi(z)\\ &\le\frac{d_{\mathrm W}(W,Z)}{\delta} +\int_z^{z+\delta}\frac{z+\delta-t}{\delta}\varphi(t)\,dt\\ &\le\frac{d_{\mathrm W}(W,Z)}{\delta}+\frac{M\delta}{2}. \end{aligned}

A ramp on $[z-\delta,z]$ gives the same bound for the opposite difference. Minimizing over $\delta>0$ yields

\boxed{ d_{\mathrm K}(W,Z)\le\sqrt{2M\,d_{\mathrm W}(W,Z)} =\left(\frac2\pi\right)^{1/4}\sqrt{d_{\mathrm W}(W,Z)}. }

If $d_{\mathrm W}=0$ , take $\delta\downarrow0$ . Otherwise the minimizing value is $\delta=\sqrt{2d_{\mathrm W}/M}$ . For the path example this gives a Kolmogorov bound of order $n^{-1/4}$ , losing a square root relative to the Wasserstein rate.

6. Chen–Shao: A direct Berry–Esseen bound

The preceding smoothing argument turns a Wasserstein rate into a weaker distribution-function rate. To avoid that loss, we can work directly with $h_z(w)=\mathbf1\{w\le z\}$ . Its Stein solution satisfies

f_z'(w)-wf_z(w)=\mathbf1\{w\le z\}-\Phi(z),

with the derivative at $z$ defined by this equation. The derivative now has an indicator discontinuity, so the earlier global Lipschitz bound on $f_z'$ cannot be used. In the integral remainder, the indicator part satisfies

\left|\int_0^\eta \{\mathbf1\{W-t\le z\}-\mathbf1\{W\le z\}\}\,dt\right| \le|\eta|\,\mathbf1\{|W-z|\le|\eta|\}.

The new task is to control probability in a short interval around $z$ , including intervals whose widths depend on the local variables. This is the role of the concentration inequalities in Chen and Shao (2004), Sections 3–4.

Nested local-dependence conditions

Continue to use normalized summands $\xi_i=X_i/\sigma$ , so that $\operatorname{Var}(\sum_i\xi_i)=1$ . For a set $A$ , write $\xi_A=(\xi_j)_{j\in A}$ and let $A^c$ denote its complement in $\{1,\ldots,n\}$ . The local-dependence conditions are

\begin{array}{ll} \mathrm{LD1}:&\xi_i\perp\!\!\!\perp\xi_{A_i^c},\\[3pt] \mathrm{LD2}:&\mathrm{LD1}\ \text{and}\quad \xi_{A_i}\perp\!\!\!\perp\xi_{B_i^c},\\[3pt] \mathrm{LD3}:&\mathrm{LD2}\ \text{and}\quad \xi_{B_i}\perp\!\!\!\perp\xi_{C_i^c}, \end{array} \qquad i\in A_i\subseteq B_i\subseteq C_i.

The conditions successively require independence for an observation, its first neighborhood, and a larger block. A dependency graph supplies these separations by taking

A_i=N_i,\qquad B_i=\bigcup_{j\in A_i}N_j,\qquad C_i=\bigcup_{j\in B_i}N_j.

For general local-dependence models, LD1 alone does not justify these larger-block independence statements.

Theorem 2: Chen–Shao’s uniform bound

Assume LD3 and finite $p$ th absolute moments for some $2<p\le3$ . Define

\mathcal N(C_i)=\{j:B_j\cap C_i\ne\varnothing\},\qquad \kappa=\max_i\max\left\{ |\mathcal N(C_i)|,\ |\{j:i\in C_j\}| \right\}.

Then Chen–Shao, Theorem 2.4 gives

\boxed{ d_{\mathrm K}(W,Z) \le75\kappa^{p-1}\sum_i\mathbb E|\xi_i|^p =\frac{75\kappa^{p-1}}{\sigma^p} \sum_i\mathbb E|X_i|^p. }

Unlike the fourth-moment graph bound, this result controls distribution functions directly and permits $p\le3$ . Its neighborhood parameter $\kappa$ differs from $D$ . It also counts how enlarged neighborhoods intersect and how many of them contain a given index, as specified above. We quote the theorem rather than reproduce its proof. The indicator-remainder calculation explains why the earlier Taylor argument alone is insufficient.

For the path example, choose $A_i$ , $B_i$ , and $C_i$ to have radii one, two, and three. Then

\begin{aligned} \mathcal N(C_i)&\subseteq\{j:|j-i|\le5\}, &|\mathcal N(C_i)|&\le11,\\ \{j:i\in C_j\}&\subseteq\{j:|j-i|\le3\}, &|\{j:i\in C_j\}|&\le7. \end{aligned}

Taking $p=3$ , $\kappa\le11$ , $\sigma^2=4n-2$ , and $\mathbb E|X_i|^3=4$ therefore gives

d_{\mathrm K}\left(\frac{S}{\sqrt{4n-2}},Z\right) \le\frac{75\cdot11^2\cdot4n}{(4n-2)^{3/2}} =O(n^{-1/2}).

The rate improves on the $n^{-1/4}$ obtained by smoothing our Wasserstein bound, although the displayed numerical constant is large. This is a comparison for this example, not a claim that every Chen–Shao bound is numerically sharper than every graph bound.

More generally, if $\kappa_n$ is bounded, $\sup_{n,i}\mathbb E|X_{ni}|^p<\infty$ , and $\sigma_n^2\ge cn$ , then

d_{\mathrm K}(W_n,Z) \le C n^{1-p/2}\longrightarrow0.

7. What is still needed for statistical inference?

The earlier doubly robust note separates a population identity from estimation error. A dependence CLT requires the same separation. For a target $\theta_n$ , suppose an estimator $\widehat\theta_n$ admits

n(\widehat\theta_n-\theta_n) =\sum_{i=1}^nX_{ni}+r_n, \qquad r_n=o_{\mathbb P}(\sigma_n),

with centered leading summands satisfying one of the preceding CLTs. Then

\frac{n(\widehat\theta_n-\theta_n)}{\sigma_n} =W_n+o_{\mathbb P}(1) \Rightarrow N(0,1).

If, in addition, a positive estimator $\widehat\sigma_n$ of $\sigma_n$ satisfies $\widehat\sigma_n/\sigma_n\to_{\mathbb P}1$ , Slutsky's theorem gives

\frac{n(\widehat\theta_n-\theta_n)}{\widehat\sigma_n} \Rightarrow N(0,1).

The dependency graph must describe these leading summands, not just the observed network. Shared fitted nuisance functions can introduce dependence beyond graph neighbors; a separate expansion and remainder argument is then required. Likewise, the CLT does not itself prove consistency of $\widehat\sigma_n$ .

For a random graph, the deterministic-graph theorem can instead be applied conditionally when its centering, independence, moment, and positive-variance conditions hold given that graph. The conditional approximation error must tend to zero, and the normalization must use the corresponding conditional variance. Randomness of the graph alone does not verify those conditions.

References

Nathan Ross (2011). Fundamentals of Stein’s method. Lemma 2.5 supplies the Stein factors; Section 3.2, Theorem 3.5, supplies the dependency-neighborhood bound.
Louis H. Y. Chen and Qi-Man Shao (2004). Normal approximation under local dependence. The Annals of Probability, 32(3A), 1985–2028. Section 2 defines LD1–LD3; Theorem 2.4 gives the uniform Berry–Esseen bound used here, with concentration inequalities and proofs in Sections 3–4.