# Help in understanding solution of an expected value problem

I don't understand the solution for this problem. From Wikipedia, I read that if a random variable $X$ takes value $x_1$ with probability $p_1$, $x_2$ with probability $p_2$ and so on, then the expectation of $X$ is defined as

$E[X] = x_1p_1 + x_2p_2 +...+x_kp_k$

For the question linked, $X$ = Number of unordered cycles of length 3. Cycle of length 3 can be formed in $\binom {8}{3}$ ways. So $X$ can take values from $0$ to $56$. Then for calculating the expected value, we would have to consider the probabilities of getting $0$ to $56$ cycles. But the solution posted there is much simpler and I don't understand it. Thanks for helping.

• The expectation can be found the way you describe, i.e. by making use of the distribution of $X$. But in many cases they can be found on a more direct way. Quite often it is "easy" to find expectations and "difficult" to find distributions. – drhab Mar 16 '15 at 14:48

The formula from Wikipedia is certainly correct, however computing all these probabilities is a mess in case of the problem with cycles. It is in fact often the case in similar problems - for example, you randomly put $n$ boys and $n$ girls around the round table, and ask what is the expected number of boy-girl pairs do over there.

Imagine that you need to solve a general problem of the kind: count expected number of good things. There are two ways to approach that: first, which you've described. Assume that there are $m$ things in total, then $$E[\text{number of good things}] = \sum_{k = 0}^m k \cdot P(\text{there are exactly }k\text{ good things})$$ and the second: \begin{align} E[\text{number of good things}] &= E\left[\sum_{k=1}^m 1\{\text{thing number }k\text{ is good}\}\right] \\ & = \sum_{k=1}^m P(\text{thing number }k\text{ is good}) \end{align} which is often a much faster solution in case of problems that posses symmetry.

• I dont understand the second formula. Can you please explain it with a small example. – Stupid Man Mar 18 '15 at 14:48

Let $\mathcal S:=\{s\in\wp(\{1,\dots,8\})\mid |s|=3\}$. This way any element of $\mathcal S$ can be identified as three distinct vertices.

For $s=\{i,j,k\}\in\mathcal S$ define random variables $X_s$ taking value $1$ if the edges $(i,j),(i,k),(j,k)$ are present and $0$ otherwise. Then $X=\sum_{s\in\mathcal S}X_s$ and consequently $\mathbb EX=\sum_{s\in\mathcal S}\mathbb EX_s$.

Because of symmetry $\mathbb EX_s=\mathbb EX_{\{1,2,3\}}$ for each $s\in\mathcal S$ and consequently $\mathbb EX=\binom83\times\mathbb EX_{\{1,2,3\}}$.

It remains to find $\mathbb EX_{\{1,2,3\}}$ wich is the probability that the edges $(1,2),(1,3),(2,3)$ are present.