Uncorrelatedness of nonincident arcs in uniformly random DAGs

The primary source's arc variables are signed trinomial variables, not Boolean edge-presence indicators. In the notation of its equation (4), set

$$X_{ij}(G)= \begin{cases} 1,&i\to j\text{ belongs to }G,\\ -1,&j\to i\text{ belongs to }G,\\ 0,&\text{neither arc belongs to }G, \end{cases} \qquad X_{ji}=-X_{ij}.$$

Let $G$ be uniformly distributed over all labeled directed acyclic graphs on $[n]$. More generally, the following proof applies to every vertex-exchangeable distribution on directed graphs with no oppositely oriented parallel arcs.

For any distinct $i,j$, the vertex transposition $\tau=(ij)$ preserves the distribution and satisfies

$$X_{ij}(\tau G)=-X_{ij}(G).$$

Consequently $\mathbb E X_{ij}=0$. If $i,j,k,l$ are distinct, the same transposition fixes $X_{kl}$. Therefore

$$\mathbb E[X_{ij}X_{kl}] =\mathbb E[X_{ij}(\tau G)X_{kl}(\tau G)] =-\mathbb E[X_{ij}X_{kl}],$$

and hence

$$\boxed{\operatorname{Cov}(X_{ij},X_{kl})=0.}$$

This proves Conjecture 3.1 for every $n$; neither acyclicity nor uniformity is needed beyond vertex-exchangeability.

A stronger classification follows. Write $M=\binom n2$, $v=\mathbb E X_{12}^{2}$, $c=\mathbb E[X_{12}X_{13}]$, and let $B$ be the oriented vertex-edge incidence matrix of the complete graph. Exchangeability and the vanishing just proved give

$$\Sigma=(v-2c)I_M+cB^{\mathsf T}B.$$

Since $BB^{\mathsf T}=nI_n-\mathbf1\mathbf1^{\mathsf T}$, the two covariance eigenvalues are $v+(n-2)c$, with multiplicity $n-1$, and $v-2c$, with multiplicity $M-n+1$.

Source: M. Scutari, “On the Prior and Posterior Distributions Used in Graphical Modelling,” Bayesian Analysis 8 (2013), 505–532, equation (4) and Conjecture 3.1, doi:10.1214/13-BA819.