Correlation for random graph (Erdos-Renyi)

Question

Consider $n$ vertices labeled $1, 2, . . . , n$ and suppose that between each of the $n$ pairs of distinct $2$ vertices an 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 $ρ(D_i,D_j)$, the correlation between $D_i$ and $D_j$.

I know that $ρ(D_i,D_j) = \frac{cov(D_i,D_j)}{\sqrt(Var(D_i)Var(D_j))} = \frac{E[D_iD_j]-E[D_i]E[D_j]}{\sqrt((E[D_j^2]-E[D_j]^2)(E[D_i^2]-E[D_i]^2)}$.

I can define a random variable $X_{ij}$ to be the indicator function denoting whether there is an edge between i and j. So $D_i = \sum{_{j=1, j≠i}^k}X_{ij}$. So the $E[D_i] = E[\sum{_{j=1, j≠i}^k}X_{ij}] = \sum{_{j=1, j≠i}^k}E[X_{ij}]$. I'm not quite too sure where to go from here.

Answer 1

You employ linearity of expectation. $$ \mathbb E[D_i] = \mathbb E\left[\sum_{k \ne i} X_{ik}\right] = \sum_{k \ne i} \mathbb E[X_{ik}] = \sum_{k \ne i} p = (n-1)p. $$ You can do the same thing with $\mathbb E[D_i D_j]$ and $\mathbb E[D_i^2]$, too; the expression inside the expected value will be the product of two sums, which you'll have to distribute first.

Alternatively, you can think of it this way. The quantity $D_i D_j$ counts the number of ordered pairs $(e_1, e_2)$ where $e_1$ is an edge with endpoint $i$ and $e_2$ is an edge with endpoint $j$. There are:

• $(n-2)^2$ ordered pairs $(k,\ell)$ of vertices that are neither $i$ nor $j$, and for each of them, the ordered pair $(ik, j\ell)$ contributes $1$ to $D_i D_j$ with probability $p^2$: the probability that both of those edges occur in the random graph.
• $2(n-2)$ more ordered pairs where one of the edges is $ij$, but the other isn't; these work the same way.
• one ordered pair $(ij, ij)$ which contributes $1$ if there is an edge between vertices $i$ and $j$: this happens with probability $p$.

Adding these up, we get $\mathbb E[D_i D_j] = (n-2)^2 p^2 + 2(n-2)p^2+ p$, or $n(n-2)p^2 + p$. We can compute $\mathbb E[D_i^2]$ by the same strategy, but it's easier because the vertex $j$ does not need to be treated separately.