1
$\begingroup$

So the problem is: A fair coin is tossed repeatedly. Let us denote heads by H and tails by T. What is the expected number of tosses until we observe HTT?

My solution: Consider Markov chain with transition probability with state space
{$HHH,HHT,HTH,HTT,THH,THT,TTH,TTT$}:

$$ \begin{bmatrix}0.5 &0.5&0&0&0&0&0&0 \\0 & 0&0.5&0.5&0&0&0&0\\0&0&0&0&0.5&0.5&0&0\\0&0&0&0&0&0&0.5&0.5\\0.5 &0.5&0&0&0&0&0&0 \\0 & 0&0.5&0.5&0&0&0&0\\0&0&0&0&0.5&0.5&0&0\\0&0&0&0&0&0&0.5&0.5\end{bmatrix}$$

Let $g(XXX)$ be the average time for the Markov chain to go from state $XXX$ to state $HTT$. Then,

$g(HTT)=0$

$g(HHH)=g(THH)=0.5g(HHH)+0.5g(HHT)+1$

$g(HHT)=g(THT)=0.5g(HTH)+0.5g(HTT)+1$

$g(HTH)=g(TTH)=0.5g(THH)+0.5g(THT)+1$

$g(TTT)=0.5g(TTH)+0.5G(TTT)+1$

Then

$g(HHH)=g(HHT)+2$

$g(HHT)=0.5g(HTH)+1$

$g(HTH)=g(HHH)+2$

$g(TTT)=g(HTH)+2$

Then,

$ g(THH)=g(HHH)=8 $

$g(HHT)=g(THT)=6$

$g(HTH)=g(TTH)=10$

$ g(TTT)=12$

So the average number of tosses to get $HTT$ is equivalent to $g(THH)=8$

Is the answer right? Is there an easier way other than solving a system equation?

$\endgroup$
1
$\begingroup$

Consider a sequence of $n$ coin tosses. Let $X_i = 1$ if tosses numbered $i$ through $i+2$ are HTT, $X_i = 0$ otherwise.

Then $E(X_i) = \frac18.$ Moreover, although $X_i$ and $X_{i+1}$ are not independent, the expectation of their sum is still the sum of their expectations. We can extend this to show that $$E(X_1 + \cdots + X_{n-2}) = E(X_1) + \cdots + E(X_{n-2}) = \frac{n-2}{8}.$$

As $n\to\infty,$ in the limit $\frac18$ of the three-toss sequences are HTT, and each new coin toss adds a three-toss sequence to the list, hence the mean waiting time between HTTs is $8$ coin tosses.

The expected waiting time between HTTs is $8$ despite the fact that after observing HTT, the next two coin tosses have zero probability of producing another HTT. Hence the expected waiting time after no coin tosses is also $8.$

To make this argument formal we might need to get into something like your Markov chain. But as long as we consider it "obvious" that the mean waiting time exists (perhaps because we know we can turn this into a Markov chain), I think it is also "obvious" that the mean is $8$ when there have been at least two previous coin tosses.


Note that the argument presented above does not apply to every three-letter sequence of H and T, but only to those sequences $\sigma$ for which the statement "after observing $\sigma,$ the next two coin tosses have zero probability of producing another $\sigma$" is true. In other cases, the argument must be modified to take into account the possibility of overlapping observations of the sequence.

For example, after observing HTH there is a $\frac14$ probability of observing HTH again after exactly $2$ more flips. The expected waiting time between repetitions of HTH is therefore $8 = \frac14\cdot2 + \frac34 W_{HTH},$ where $W_{HTH}$ is the expected waiting time for HTH starting from no previous coin tosses, and therefore $W_{HTH} = 10.$

For HHH, there is a $\frac12$ chance to observe the sequence again after just $1$ toss, and a $\frac12$ chance that the next toss will be T, after which the expected waiting time for the next HHH is $W_{HHH},$ the same as the expected waiting time with no previous tosses, so the expected time between repetitions is $8 = \frac12\cdot1 + \frac12(1+W_{HHH}),$ from which we get $W_{HHH} = 14.$

$\endgroup$
  • $\begingroup$ This "obvious" argument might not be so obvious since it relies crucially on the never mentioned fact that no suffix of HTT is a prefix of this word. $\endgroup$ – Did Mar 9 '17 at 6:51
  • $\begingroup$ @Did Never mentioned? "[A]fter observing HTT, the next two coin tosses have zero probability of producing another HTT." But it may be worth emphasizing how essential that statement is to the argument, so I have added some discussion about that. $\endgroup$ – David K Mar 9 '17 at 13:27
  • $\begingroup$ Curiously, $12$ is the smallest even number which is not the answer to this sort of question. Examples of other answers include $H:2$, $HT:4$, $HH:6$, $HTT:8$, $HTH:10$, $HHH:14$, $HTTT:16$, $HTTH:18$, $HTHT:20$ $\endgroup$ – Henry Feb 5 at 22:46

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.