Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$.

share|cite|improve this question
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
up vote 3 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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