# Find the correlation between $D_i$ and $D_j$

Consider a graph having n = 8 vertices labeled $$1,2,...,8$$. Suppose that each edge is independently present with probability $$p$$. The degree of vertex $$i$$, designated as $$D_i$$, is the number of edges that have vertex $$i$$ as one of its vertices. Find $$Corr(D_i,D_j)$$, the correlation between $$D_i$$ and $$D_j$$.

My Attempt

The formula for correlation is $$Corr(X,Y)=\frac{Cov(X,Y)}{\sqrt{Var(X)Var(Y)}}=\frac{\mathbb{E}[XY]-\mathbb{E}[X]\mathbb{E}[Y]}{\sqrt{Var(X)Var(Y)}}$$

I'm not sure what kind of distribution to model $$D_i$$ and $$D_j$$ as. Should we split $$D_i$$ up into indicator variables? Where $$I=\begin{cases}1&\text{if edge (i,j) is present}\\0&\text{otherwise}\end{cases}$$ Then make the $$D=\sum^{8}_{i=1} I_i$$. This makes the most sense to me, but I'm not sure how to proceed or if this is even the right approach.

• I made a crucial mistake in my old answer; see my edit. Commented Jun 5, 2021 at 4:31

$$\begin{split}\rho(D_i, D_j)&=\frac{Cov(D_i,D_j)}{\sqrt{Var(D_i)Var(D_j)}}\\ &=\frac{Var(I_{ij})}{\sqrt{Var(D_i)Var(D_j)}}\\ &=\frac{p(1-p)}{\sqrt{7p(1-p)\cdot 7p(1-p)}}\\ &=\frac17\end{split}$$

The second equality comes from the fact that the covariance between edges is 0 unless the edge is the same. The third: $$I_{ij}$$ is bernoulli with parameter $$p$$, and $$D_i$$ and $$D_j$$ are binomial with parameters $$7$$ and $$p$$.

• How did you find the variance of $D_i$ to be $7p(1-p)$? Where did the $7$ come from Commented Jun 6, 2021 at 3:24
• $D_i\sim \text{Binomial}(7, p)$ because each edge has probability $p$ of being included and there are 7 other nodes that node $i$ can form an edge with.
– Vons
Commented Jun 6, 2021 at 4:33

Here's a sketch; if I have time, I'll complete this later.

I denote $$I = I_{ij}$$.

Let $$E_{ij}$$ be the edge from vertex $$i$$ to $$j$$. We know that $$\mathbb{P}(E_{ij}\text{ is present}) = \mathbb{P}(I_{ij} = 1) = p$$. In fact, we know that there are $$7 + 6 + \cdots + 1 = 28$$ possible edges, so that $$\mathbb{P}(E_{ij}\text{ is present}) = \mathbb{P}(I_{ij} = 1) = p = \dfrac{1}{28}\text{.}$$ The degree of vertex $$i$$ is thus given by $$D_i = \sum_{k \neq i}I_{ik}$$ where for each $$i$$, there are $$7$$ terms in the summation. Hence $$\text{Cov}(D_i, D_j) = \text{Cov}\left(\sum_{k \neq i}I_{ik}, \sum_{\ell \neq j}I_{j\ell} \right) = \sum_{k \neq i}\sum_{\ell \neq j}\text{Cov}(I_{ik}, I_{j\ell})$$ For computing the covariance, $$\mathbb{E}[I_{ik}]$$ and $$\mathbb{E}[I_{j\ell}]$$ are easy to compute. For $$\mathbb{E}[I_{ik}I_{j\ell}]$$, note that $$I_{ik}I_{j\ell} = 1$$ if and only if $$I_{ik} = 1$$ and $$I_{j\ell} = 1$$, then use independence to calculate it. We don't care about the other cases, since otherwise, $$I_{ik}I_{j\ell} = 0$$ and they do not add to $$\mathbb{E}[I_{ik}I_{j\ell}]$$.