Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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...??

share|cite|improve this question
Have you tried finding a recursion? – Qiaochu Yuan Nov 15 '12 at 5:33
Wow, I haven't learnt till that. My syllabus for statistics covered up till binomial and Poisson distribution so far. Also, elementary probability. – Yellow Skies Nov 15 '12 at 5:39
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? – ShreevatsaR Nov 15 '12 at 6:48
Good question, I also want to know the answer for this GEM2900 graded quiz question due tomorrow. – user49514 Nov 15 '12 at 8:46
@cpy Fascinating. – Did Nov 15 '12 at 9:23
up vote 5 down vote accepted

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.

share|cite|improve this answer

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$.

share|cite|improve this answer
Why give the numerical result instead of hints? – Did Nov 15 '12 at 9:22
@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 – Henry Nov 15 '12 at 20:54

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.