0
$\begingroup$

If we have a random graph $G \in g(n,\frac{1}{2})$ how do we show that the expected number of edges is $\frac{1}{2} {{n}\choose{2}}$

Thanks in advance

$\endgroup$
  • $\begingroup$ Are you talking about the model in which for every (unordered( pair $\{u,v\}$ of vertices we decide independently, with probability $1/2$, whether or not there is an edge joining $u$ and $v$? Then it should not be hard, there are $\binom{n}{2}$ pairs. $\endgroup$ – André Nicolas May 11 '13 at 6:59
1
$\begingroup$

Let $\mathbb{I}_k$ be the indicator function for the edge $k$, i.e., $$\mathbb{I}_k = \begin{cases}1 & \text{ if $k^{th}$ edge is present}\\ 0 & \text{ if $k^{th}$ edge is not present} \end{cases}$$ The quantity you are interested in is \begin{align} \mathbb{E}\left(\sum_{k=1}^{\binom{n}2} \mathbb{I}_k\right) & = \sum_{k=1}^{\binom{n}2} \mathbb{E}\left(\mathbb{I}_k\right) \left(\because \text{By linearity of expectation} \right)\\ & = \sum_{k=1}^{\binom{n}2} \mathbb{P}\left(\mathbb{I}_k=1\right) = \sum_{k=1}^{\binom{n}2} \mathbb{P}\left(\text{$k^{th}$ edge is present}\right)\\ & = \sum_{k=1}^{\binom{n}2} \dfrac12 \left(\text{Assuming that it is equally likely for an edge to be present or absent} \right)\\ & = \dfrac12 \dbinom{n}2 \end{align}

$\endgroup$
0
$\begingroup$

HINT: You have $^nC_2$ edges with probability of connecting = $\frac{1}{2}$. So the result.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy