# Expected Number of edges in the graph

G(V,E) is a simple graph with 8 vertices. The edges of G are decided by tossing the coin for each 2 vertices combination. Edge is added between any two vertices iff head is turned up. Expected number of edges in the Graph G(V,E) is.

I thought of doing like this

Let X be a random variable denoting the number of edges in the graph.

Total possible edges->$$_8C_2=28$$

Now, for each of those 28 edges, we tossed a coin and if it turned out to be heads,that edge was included.

(1)X=0,P(X)=$$_{28}C_0 \frac{1}{2^{28}}$$. All those 28 tosses of coin are independent with probability of heads=Probability of getting tails=$$\frac{1}{2}$$

(2)X=1(One edge), P(X)=$$_{28}C_1 \times\frac{1}{2} \times \frac{1}{2^{27}}$$-Means in those 28 trials, exactly 1 heads and rest tails.

(3)Similarly for all 28 edges-> $$X=28,P(X)=_{28}C_{28} \times \frac{1}{2^{28}}$$

And then we add all cases of X from 0 to 28 because $$E[X]=\sum x.p(x)$$

But this all together seems to be a very huge number and answer is given to be 14, where I am wrong in my reasoning?

• Two remarks: (1) What you tried to write, is not very clear. You do not define what the $C_0,C_1,C_2,...$ are. (2) The problem becomes much simpler if you were to use the linearity of the expectation. By finding a collection of 'simple' random variables for which the calculation of expectation is simple, and that sum up to $X$, you will have simplified the problem many times over. – Keen-ameteur Dec 17 '18 at 6:31
• It is not such a "very huge number" because the factor $\frac1{2^{28}}$ is pretty small. – bof Dec 17 '18 at 7:06

In other words, you want to know the expected number of times you're going to get heads in $$28$$ independent tosses of a fair coin. To do it your way, you can add up the $$29$$ terms by hand, or you can use the identity $$\sum_{k=0}^nk\binom nk=n2^{n-1}\tag1$$ which is obtained by differentiating the binomial identity $$(1+x)^n=\sum_{k=0}^n\binom nkx^n$$ with respect to $$x$$ and then setting $$x=1$$. Using $$(1)$$ we get $$E(X)=\sum_{k=0}^{28}k\binom{28}k\left(\frac12\right)^k\left(\frac12\right)^{28-k}=\left(\frac12\right)^{28}\sum_{k=0}^{28}k\binom{28}k=\left(\frac12\right)^{28}\cdot28\cdot2^{27}=14.$$
This shows that, if you toss a coin $$28$$ times, on average you're going to get $$14$$ heads. You can get the same result more easily by using the additivity of expectations: if $$X$$ is the sum of $$28$$ random variables, each of which has an expected value of $$\frac12$$, then the expected value of $$X$$ is $$28\cdot\frac12=14$$.
• Another way to find $\sum_{k=0}^n k \binom nk$ is to substitute $\binom nk = \frac nk \binom{n-1}{k-1}$ in all except the $k=0$ term, getting $\sum_{k=1}^n n \binom{n-1}{k-1} = n \sum_{j=0}^{n-1}\binom{n-1}{j} = n2^{n-1}$. – Misha Lavrov Dec 18 '18 at 4:18