This might be a very simple question. But I was going through this lecture where it is mentioned that

If I have n-1 neighbors and there is a probability p of having an edge with a neighbor. Then the average degree of any node is given by (n-1)*p. This is fine I get it

But how come the variance of degree is (n-1)p(1-p). I didn't get how this variance was derived.

  • 4
    $\begingroup$ There is most likely an assumption that the events $A_i = \text{"I have an edge with neighbor}~i"$ are $n-1$ mutually independent events, making the degree a binomial random variable with parameters $(n-1,p)$. The result then follows from the properties of binomial random variables. If you want an explicit derivation, use the result that $$\text{var}(X) = E[X(X-1)] + E[X] - (E[X])^2$$ since $E[X(X-1)]$ is easier to compute for a binomial random variable than the $E[X^2]$ needed for applying the standard result $$\text{var}(X) = E[X^2] - (E[X])^2.$$ $\endgroup$ – Dilip Sarwate Dec 21 '12 at 16:56
  • $\begingroup$ what is E[X(X-1)]] for a binomial distribution how is it calculated? $\endgroup$ – user34790 Dec 21 '12 at 20:58
  • 1
    $\begingroup$ $$E[X(X-1)]=\sum_{i=0}^{n-1}i(i-1)\binom{n-1}{i}p^i(1-p)^{n-1-i} = \sum_{i=2}^{n-1}i(i-1)\binom{n-1}{i}p^i(1-p)^{n-1-i}$$ since the first two terms of the middle sum are $0$. Now write $\binom{n-1}{i}=\frac{(n-1)!}{i!(n-1-i)!}$, cancel $i(i-1)$ and simplify. $\endgroup$ – Dilip Sarwate Dec 21 '12 at 22:04

A very easy way to calculate the variance is to see that it is a sum of independent Bernoulli random variables, one for each neighbor. The variance of a $\text{Bernoulli}(p)$ random variable is $p(1-p)$. The variance of a sum of independent random variables is the sum of the variances.


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.