2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Qiaochu Yuan May 5 '13 at 5:12
4
$\begingroup$

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.

$\endgroup$

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.