A Worked Dependency-Graph Bound for Indicators

From a Dependency Graph to a Numerical Bound

A dependency graph turns a qualitative description of dependence into a usable parameter for normal approximation. To apply the resulting theorem in a concrete problem, one must do more than identify a graph: the mean and variance of the sum must be calculated, the graph parameter must match the theorem’s convention, and the error bound must be evaluated after standardization.

We work with indicator variables. This makes the moment terms in the theorem explicit, while still allowing substantial dependence between the indicators. Two small examples will show how strongly the variance and the final numerical bound depend on the joint distribution.

Dependency Graphs and the Bound

Definition: Let \(I_1,\ldots,I_n\) be random variables taking values in \(\{0,1\}\). A 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 graph edge joining a vertex of \(A\) to a vertex of \(B\), the random vectors \((I_i)_{i\in A}\) and \((I_j)_{j\in B}\) are independent. Write \(N_i\) for vertex \(i\) together with all its neighbors, and set \(D=\max_i |N_i|\).

The closed-neighborhood convention matters: an isolated vertex has \(|N_i|=1\), so \(D=1\) for an empty graph. A complete graph on \(n\) vertices has \(D=n\). Using the maximum degree without adding one would change the parameter in the bound below.

Let \(p_i=\mathbb{E}I_i\), \(S=\sum_{i=1}^n I_i\), and \(\sigma^2=\operatorname{Var}(S)\). For \(\sigma^2>0\), write \(W=(S-\mathbb{E}S)/\sigma\). Let \(Z\) be standard normal, and define the Wasserstein distance by taking the supremum of \(|\mathbb{E}h(W)-\mathbb{E}h(Z)|\) over all real-valued 1-Lipschitz functions \(h\).

Theorem (dependency-graph normal-approximation bound): If \(I_1,\ldots,I_n\) are indicators with dependency graph \(G\), \(D\) is the maximum closed-neighborhood size, and \(\sigma^2=\operatorname{Var}(S)>0\), then

d_W\left(\frac{S-\mathbb{E}S}{\sigma},Z\right) \leq \frac{4D^2}{\sigma^3}\sum_{i=1}^n \mathbb{E}|I_i-p_i|^3.

This is a convenient indicator form of the dependency-graph normal-approximation bound. Its right-hand side is an upper bound, not necessarily a sharp estimate of the actual distance. In particular, a value larger than one is not a contradiction: Wasserstein distance is not restricted to the interval \([0,1]\).

Two Calculations Used in Every Example

First, the variance can be calculated from the graph and the pairwise covariances. Variables at nonadjacent vertices are independent: apply the dependency-graph condition to the two singleton sets. Their covariance is therefore zero.

Proposition: For a dependency graph \(G\),

\operatorname{Var}(S) = \sum_{i=1}^n p_i(1-p_i) + 2\sum_{\substack{i<j\\ \{i,j\}\text{ is an edge of }G}} \operatorname{Cov}(I_i,I_j).

Proof. Expanding the variance of a finite sum gives

\operatorname{Var}(S) = \sum_{i=1}^n \operatorname{Var}(I_i) + 2\sum_{i<j}\operatorname{Cov}(I_i,I_j).

Since \(I_i\) is an indicator, \(\operatorname{Var}(I_i)=p_i(1-p_i)\). If \(\{i,j\}\) is not an edge, the singleton sets \(\{i\}\) and \(\{j\}\) have no edge between them, so \(I_i\) and \(I_j\) are independent and their covariance vanishes. Removing these zero terms gives the claimed formula. \(\square\)

Second, the moment contribution of each indicator depends only on its success probability. On the event \(I_i=1\), the absolute centered value is \(1-p_i\); on the event \(I_i=0\), it is \(p_i\).

Proposition: For an indicator \(I_i\) with success probability \(p_i\),

\mathbb{E}|I_i-p_i|^3 = p_i(1-p_i)\bigl((1-p_i)^2+p_i^2\bigr).

Proof. The two possible values of \(I_i\) give

\mathbb{E}|I_i-p_i|^3 = p_i|1-p_i|^3+(1-p_i)|0-p_i|^3.

Because \(0\leq p_i\leq1\), this becomes

p_i(1-p_i)^3+(1-p_i)p_i^3 = p_i(1-p_i)\bigl((1-p_i)^2+p_i^2\bigr),

as required. \(\square\)

Worked Example: Two Dependent Indicators

Worked Example: A Two-Vertex Dependency Graph

Let \((I_1,I_2)\) have probabilities

\mathbb{P}((I_1,I_2)=(1,1))=\frac18,\quad \mathbb{P}((I_1,I_2)=(1,0))=\frac18,\quad \mathbb{P}((I_1,I_2)=(0,1))=\frac18,\quad \mathbb{P}((I_1,I_2)=(0,0))=\frac58.

These probabilities sum to \(1\). Each indicator has success probability \(p_i=1/8+1/8=1/4\). Use the graph with one edge joining the two vertices. It is a dependency graph; because its only distinct vertices are joined, there are no nonempty disjoint vertex sets with no edge between them. Its maximum closed-neighborhood size is \(D=2\).

The joint success probability is \(1/8\), so

\operatorname{Cov}(I_1,I_2) = \mathbb{E}(I_1I_2)-\mathbb{E}I_1\,\mathbb{E}I_2 = \frac18-\frac1{16} = \frac1{16}.

The variance formula therefore gives

\mathbb{E}S=\frac12,\qquad \sigma^2 = 2\left(\frac14\cdot\frac34\right)+2\left(\frac1{16}\right) = \frac38+\frac18 = \frac12.

For either indicator, the centered absolute third moment is

\mathbb{E}|I_i-p_i|^3 = \frac14\cdot\frac34\left(\left(\frac34\right)^2+\left(\frac14\right)^2\right) = \frac{3}{16}\cdot\frac{10}{16} = \frac{15}{128}.

Thus the sum of the two moment terms is \(30/128=15/64\). Applying the theorem and evaluating the denominator explicitly,

d_W\left(\frac{I_1+I_2-\frac12}{\sqrt{1/2}},Z\right) \leq \frac{4(2)^2(2)(15/128)}{(1/2)^{3/2}} = \frac{15/4}{1/(2\sqrt{2})} = \frac{15\sqrt{2}}{2}.

The large numerical value is a valid, though uninformative, upper bound for this small example. It should not be read as a claim that the actual distance equals the right-hand side.

Worked Example: Three Indicators with a Complete Graph

Worked Example: Choosing a Joint Law to Compute the Variance

Choose a random pair uniformly from the three pairs \(\{1,2\}\), \(\{1,3\}\), and \(\{2,3\}\) with probability \(3/8\) in total, so each pair has probability \(1/8\). Set the two indicators indexed by that pair equal to one and the remaining indicator equal to zero. With the remaining probability \(5/8\), set all three indicators equal to zero.

For each \(i\), two of the three equally likely pairs contain \(i\). Hence \(\mathbb{P}(I_i=1)=2(1/8)=1/4\). For distinct \(i,j\), exactly one pair contains both, so \(\mathbb{E}(I_iI_j)=1/8\) and \(\operatorname{Cov}(I_i,I_j)=1/8-1/16=1/16\). Take the complete graph on three vertices, a dependency graph with \(D=3\).

Using the variance formula, including all three edge covariances,

\mathbb{E}S=\frac34,\qquad \sigma^2 = 3\left(\frac14\cdot\frac34\right) + 2\cdot3\left(\frac1{16}\right) = \frac9{16}+\frac6{16} = \frac{15}{16}.

Each centered third moment is \(15/128\), so their sum is \(45/128\). The bound becomes

d_W\left(\frac{I_1+I_2+I_3-\frac34}{\sqrt{15/16}},Z\right) \leq \frac{4(3)^2(45/128)}{(15/16)^{3/2}} = \frac{405/32}{15\sqrt{15}/64} = \frac{54}{\sqrt{15}}.

Here \((15/16)^{3/2}=15\sqrt{15}/64\); keeping this factor in its exact form makes the final simplification easy to check. As in the two-variable example, the theorem gives a valid bound that is much too large to quantify approximation quality closely.

Worked Example: Independent Indicators

Worked Example: Four Fair Indicators

Let \(I_1,\ldots,I_4\) be independent indicators with success probability \(1/2\). The empty graph is a dependency graph, and each vertex has a closed neighborhood containing only itself, so \(D=1\). The mean and variance are

\mathbb{E}S=4\left(\frac12\right)=2,\qquad \sigma^2=4\left(\frac12\cdot\frac12\right)=1.

For each indicator, \(\mathbb{E}|I_i-1/2|^3=1/8\), since the absolute centered value is always \(1/2\). The sum of the four moments is \(1/2\). Therefore

d_W\left(\frac{S-2}{1},Z\right) \leq \frac{4(1)^2(1/2)}{1^3} = 2.

Even though this sum consists of independent indicators, this particular theorem and parameter choice give only a coarse numerical guarantee. A bound is useful only in context: its assumptions establish validity, while its size determines how informative it is.

How to Read the Bound Carefully

These examples illustrate three checks that prevent common errors. First, use the theorem’s stated graph convention: here \(D\) counts the vertex itself as well as its neighbors. Second, compute \(\sigma^2\) for the actual joint law, not merely by adding the individual variances when dependence is present. Third, evaluate \(\sigma^3=(\sigma^2)^{3/2}\) only after computing the variance, and simplify the numerator and denominator separately.

The theorem’s dependence on \(D^2\) also explains why a crude graph can produce a weak estimate. Adding edges preserves the dependency-graph property, but it can increase \(D\), even when the joint law has not changed. A useful analysis therefore seeks a valid graph with small closed neighborhoods, rather than automatically selecting a dense graph.

Finally, standardization is essential. The theorem controls the distance between the centered, variance-one sum and a standard normal variable. It does not directly bound the distance between \(S\) and a normal variable with arbitrary mean and variance. The positive-variance condition is also essential: if \(\sigma^2=0\), the standardized variable is not defined, so this conclusion cannot be applied.

Check Your Understanding

For each question, identify which calculation or assumption controls the answer.

Under the closed-neighborhood convention, what is \(D\) for an empty graph on four vertices, and why is it not zero?
For an indicator with success probability \(1/4\), calculate its centered absolute third moment.
In the two-indicator example, why does the covariance contribute twice in the variance of the sum?
In the three-indicator example, verify that each marginal success probability is \(1/4\), although the nonzero configurations contain two successes.
Why can the stated upper bound exceed one without contradicting the definition of Wasserstein distance?