Consider a graph with $n$ vertices, where each edge between any two vertices is independently drawn with probability $p$. Let $D_i$ be the degree of vertex $i$. What is $E[D_i \cdot D_j]$?

Here is what I did. Clearly $D_i$ and $D_j$ are not independent so we cannot just split up the product. Instead, let $C$ be the event that vertices $i$ and $j$ are connected.

$E[D_i \cdot D_j]= E[D_i \cdot D_j| C]\cdot Pr(C)+E[D_i \cdot D_j| \bar C]\cdot Pr(\bar C)$

Now $D_i$ and $D_j$ are independent, so we can simplify $E[D_i \cdot D_j]=E[D_i] \cdot E[D_j]$. Thus, we have:

$((n-2))p+1)^2\cdot p + ((n-2)p)^2\cdot (1-p)$

But this is not right. Why? How can I correct this?


If $i \neq j$ is guaranteed then your calculation looks correct. However maybe you have to assume that $i,j$ are chosen uniformly randomly so $i = j$ is a possibility, with probability $1/n$?

  • $\begingroup$ The problem assumes $i\neq j$ and says the answer is $p(1-p)+2(n-1)(p)$. I will see if these two equate to each other, but I dont think they do! $\endgroup$ – Andrew May 20 '15 at 23:40
  • $\begingroup$ It is problem 7.47 here: stat.washington.edu/~hoytak/teaching/current/stat395 $\endgroup$ – Andrew May 20 '15 at 23:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.