# Graph Theory: Conditional Expected Value of Product of two Random Variables

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$?
• 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! – Andrew May 20 '15 at 23:40