Question

Consider a graph having $n$vertices labeled$1,2,...,n$, and suppose that, between each of the $\left(\frac{n}{2}\right)$pairs of distinct vertices, an edge is independently present with probability $p$. The degree of a vertex$i$, designated as$Di,$is the number of edges that have vertex $i$as one of their vertices.

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

(b) Find $\rho (Di,Dj)$, the correlation between $Di$and$Dj$.

Short answer

a)$Di$has Binomial distribution

b)$1/(n-1)$

Step-by-step solution

Step 1:Given Information(part a)

Given that a graph has$n$vertices, probability $p$, and the degree of a vertex$i$.

Step 2:Explanation(part a)

Since vertex $i$can have an edge with outstanding$n-1$vertices autonomously and with a similar probability $p$, we have that

$D_i~\mathrm{Binom}(n-1,p)$

Step 3:Final Answer(part a)

$D_i~\mathrm{Binom}(n-1,p)$is the distribution of Di

Step 4:Given Information(part b)

Given that the degree of vertex$i,j$designated as$Di,Dj$is the number of edges that have vertex$i,j$ as one of their vertices.

Step 5:Explanation(part b)

Characterize marker irregular factors$I_k^{\left(i\right)}$and $I_k^{\left(j\right)}$that imprints assuming there exist an edge from vertex $i$to vertex $k$and from vertex $j$to vertex $k$, separately. Thus

$D_i=\sum _{k=1}^{n-1} I_k^{\left(i\right)},D_j=\sum _{k=1}^{n-1} I_k^{\left(j\right)}$

Utilizing the linearity of covariance, we have that

$\mathrm{Cov}\left(D_i,D_j\right)=\mathrm{Cov}\left(\sum _{k=1}^{n-1} I_k^{\left(i\right)},\sum _{k=1}^{n-1} I_k^{\left(j\right)}\right)$

$=\sum _{k-1}^{n-1} \sum _{l-1}^{n-1} \mathrm{Cov}\left(I_k^{\left(t\right)},I_l^{\left(j\right)}\right)$

$=p(1-p)$

At last, the correlation is equivalent to

$\rho \left(D_i,D_j\right)=\frac{\mathrm{Cov}\left(D_i,D_j\right)}{\mathrm{Var}\left(D_i\right)}=\frac{1}{n-1}$

Step 6:Final Answer(part b)

The$p(Di,Dj)$is,

$\rho \left(D_i,D_j\right)=\frac{\mathrm{Cov}\left(D_i,D_j\right)}{\mathrm{Var}\left(D_i\right)}=\frac{1}{n-1}$