Consider a graph having n vertices labeled 1, 2, . . . , n, and suppose that, between each of the $\binom{n}{2}$ pairs of distinct 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 their vertices.

(a) What is the distribution of $D_i$?

(b) Find $ρ(D_i,D_j)$, the correlation between $D_i$ and $D_j$.

My attempt is:

Let $X_{i,k} = \begin{cases}1 & \text{ if there is an edge from } i \text{ to } k\\ 0 & \text{ otherwise }\end{cases}$

$D_i=\sum_{k=1}^{n-1} x_{i,k}$=number of edges from vertex i.

$D_i$ has a binomial distribution with parameters $n-1$ and p.

$E[D_i]=E[\sum_{k=1}^{n-1} x_{i,k}]=\sum_{k=1}^{n-1} E[x_{i,k}]=(n-1)*p$

Let $X_{j,k} = \begin{cases}1 & \text{ if there is an edge from} j \text{ to }k\\ 0 & \text{ otherwise}\end{cases}$

$D_j=\sum_{k=1}^{n-1} x_{j,k}$=number of edges from vertex j.

$D_j$ has a binomial distribution with parameters $n-1$ and p.

$E[D_j]=E[\sum_{k=1}^{n-1} x_{j,k}]=\sum_{k=1}^{n-1} E[x_{j,k}]=(n-1)*p$

then I try to calculate $cov(D_i,D_j)$

$$cov(D_i,D_j)= cov (\sum_{k=1}^{n-1} x_{i,k},\sum_{w=1}^{n-1} x_{j,w})=\binom{n}{2}*(-p^2)$$ with $cov(x_{i,k},x_{j,w})= E[x_{i,k}*x_{j,w}]-E[x_{i,k}]*E[x_{j,w}]$ (and here i'm not sure) $$cov(x_{i,k},x_{j,w}) = \begin{cases}0-p^2 & if k=w \\ 0 & if k \ne w \end{cases}$$


The final result in the book is $\frac{1}{n-1} $


Notice that

$$cov(D_i, D_j)=cov\left(\sum_{k \neq i} X_{ik}, \sum_{w \neq j} X_{jw}\right)=\sum_{k \neq i} \sum_{w \neq j}cov\left( X_{ik}, X_{jw}\right)$$

$$cov(X_{ik}, X_{jw}) = \begin{cases} p-p^2 & ,k=j, w=i \\ 0 & \text{otherwise} \end{cases}$$


$$cov(D_i, D_j)=\sum_{k \neq i} \sum_{w \neq j}cov\left( X_{ik}, X_{jw}\right)=cov(X_{ij}, X_{ji})=p-p^2$$

Since $Var(D_i)=(n-1)p(1-p)$,

$$\rho(D_i, D_j)=\frac{p-p^2}{\left(\sqrt{(n-1)p(1-p)}\right)^2}=\frac{1}{n-1}$$


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.