# Expected number of edges: does $\sum\limits_{k=1}^m k \binom{m}{k} p^k (1-p)^{m-k} = mp$

Find the expected number of edges in $G \in \mathcal G(n,p)$.

Method $1$: Let $\binom{n}{2} = m$. The probability that any set of edges $|X| = k$ is the set of edges in $G$ is $p^k (1-p)^{m-k}$. So the probability that $G$ has $k$ edges is $$\binom{m}{k} p^k ( 1-p )^{m-k}$$

This implies that $$E(X) = \sum_{k=1}^m k \binom{m}{k} p^k (1-p)^{m-k}$$

Method $2$: Choose an indicator random variable $X_e : \mathcal G(n,p) \to \{ 0,1 \}$ as follows:

$$X_e(G) = \begin{cases} 1 & e \in E(G) \\ 0 & e \notin E(G) \end{cases}$$

So $E(X) = \sum_{e \in K_n} E(X_e(G)) = m p$ since each event $e \in E(G)$ and $f \in E(G)$ are independent.

How do you reconcile these answers? I'm looking for either a mistake in reasoning or a direct proof that:

$$\sum_{k=1}^m k \binom{m}{k} p^k (1-p)^{m-k} = mp$$ for $0 < p < 1$.

• You don't need independence to apply linearity of expectation. That's what makes it so wonderful! Anyway, there's nothing to reconcile. This is a correct proof of the identity you've written down. – Qiaochu Yuan May 5 '13 at 5:12

## 1 Answer

Related problems:(I), (II). Consider the function

$$f(x)=( xp+(1-p) )^m = \sum_{k=0}^{m} {m\choose k} p^k(1-p)^{m-k}x^k$$

Differentiating the above equation with respect to $x$ yields

$$\implies mp( xp+(1-p) )^{m-1} = \sum_{k=1}^{m}{m\choose k} k p^k(1-p)^{m-k}x^{k-1}.$$

Subs $x=1$ in the above equation gives the desired result.