Find the correlation between D_{i} and D_{j}

Question

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

C o r r (D_{i}, D_{j})

, the correlation between

D_{i}

and

D_{j}

.

Answer 1

Step 1

\begin{aligned} ρ (D_{i}, D_{j}) & = \frac{C o v (D_{i}, D_{j})}{\sqrt{V a r (D_{i}) V a r (D_{j})}} \\ = \frac{V a r (I_{i j})}{\sqrt{V a r (D_{i}) V a r (D_{j})}} \\ = \frac{p (1 - p)}{\sqrt{7 p (1 - p) \cdot 7 p (1 - p)}} \\ = \frac{1}{7} \end{aligned}

The second equality comes from the fact that the covariance between edges is 0 unless the edge is the same. The third:

I_{i j}

is bernoulli with parameter p, and

D_{i}

and

D_{j}

are binomial with parameters 7 and p.

Answer 2

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

I = I_{i j}

.
Let

E_{i j}

be the edge from vertex i to j. We know that

P (E_{i j} is present) = P (I_{i j} = 1) = p

. In fact, we know that there are

7 + 6 + \dots + 1 = 28

possible edges, so that

Answers (2)