Assume you toss a fair coin 25 times with the outcome of each toss being independent of the outcomes of any other toss.

How many completed runs do you expect to observe?

By definition, completed runs are a run that have been terminated by the occurrence of another symbol, and a run is defined as a sequence of completed heads or completed tails.

I have no idea how to even get started. Thanks stack!

Here's my attempt. By splitting into cases, but there are simply too many cases for me to consider. Maybe I could use binomial distribution...??

  • $\begingroup$ Have you tried finding a recursion? $\endgroup$ – Qiaochu Yuan Nov 15 '12 at 5:33
  • $\begingroup$ Wow, I haven't learnt till that. My syllabus for statistics covered up till binomial and Poisson distribution so far. Also, elementary probability. $\endgroup$ – Yellow Skies Nov 15 '12 at 5:39
  • 2
    $\begingroup$ Hint: a new run starts when a toss has a different outcome from the previous toss (or is the first one), so the number of runs is the number of tosses whose outcome is different from the previous one. Can you calculate the probability of that happening on a particular toss, and hence the expected number of the total? $\endgroup$ – ShreevatsaR Nov 15 '12 at 6:48
  • $\begingroup$ Good question, I also want to know the answer for this GEM2900 graded quiz question due tomorrow. $\endgroup$ – user49514 Nov 15 '12 at 8:46
  • $\begingroup$ @cpy Fascinating. $\endgroup$ – Did Nov 15 '12 at 9:23

Hint: For $i=1$ to $25$, let $X_i=1$ if the $i$-th toss completes a run, and let $X_i=0$ otherwise. Then $Y=X_1+X_2+\cdots+X_{25}$ is the number of runs. We want $E(Y)$.

By the linearity of expectation, we have $$E(Y)=E(X_1)+E(X_2)+\cdots +E(X_{25}).\tag{$1$}$$

Calculate $E(X_1)$. This is easy, the first toss never completes a run.

For $i \ge 2$, calculate $E(X_i)$. Then use $(1)$.

Remark: A careful reading of the questions seems to show that for example if we have HTT at the end, then TT does not count as a completed run. The usual definition of run would count TT as a run, and would have the first toss start a run. Under the usual definition of runs, the expected number is greater by $1$ than the answer you will get.


A completed run finishes when a different face turns up next.

There are $24$ times a different face can turn up next and the probability for each is $\frac{1}{2}$ so the expected number of completed runs is $24 \times \frac12$.

  • $\begingroup$ Why give the numerical result instead of hints? $\endgroup$ – Did Nov 15 '12 at 9:22
  • 1
    $\begingroup$ @did: I often give hints, but here the hints are seem to harder to understand than using the numbers to illustrate how to get the answer $\endgroup$ – Henry Nov 15 '12 at 20:54

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.