0
$\begingroup$

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.

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

2 Answers 2

2
$\begingroup$

$$\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$.

$\endgroup$
2
  • $\begingroup$ How did you find the variance of $D_i$ to be $7p(1-p)$? Where did the $7$ come from $\endgroup$ Commented Jun 6, 2021 at 3:24
  • $\begingroup$ $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. $\endgroup$
    – Vons
    Commented Jun 6, 2021 at 4:33
1
$\begingroup$

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}]$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .