2
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 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
    Commented Dec 21, 2012 at 16:56
  • $\begingroup$ what is E[X(X-1)]] for a binomial distribution how is it calculated? $\endgroup$
    – user34790
    Commented Dec 21, 2012 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
    Commented Dec 21, 2012 at 22:04

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.