1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – drhab Mar 16 '15 at 14:48
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I dont understand the second formula. Can you please explain it with a small example. $\endgroup$ – Stupid Man Mar 18 '15 at 14:48
0
$\begingroup$

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.

| cite | improve this answer | |
$\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.