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$ 12 Answers
$\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$ $\begingroup$HINT: You have $^nC_2$ edges with probability of connecting = $\frac{1}{2}$. So the result.
$\endgroup$
