# Expected Number of Coin Flips to Form a Certain Sequence

Considering an infinite sequence of tosses of a fair coin, how long will it take on average until the pattern HTT appears?

I thought one way to solve this would be as a Markov Chain, where the state it is in is defined as the number of flips away from making the sequence HTT. For example, if the sequence is HTHHT, it would be in state 1, since it only needs one more flip to form HTHHTT.

I defined the state-change matrix $$P_{ij}$$ containing the probability of transitioning from state i to state j, where i represents the row and j represents the columns. The first row is all zeroes because after HTT (state 0) appears, the sequence ends.

$$P_{ij} =\begin{bmatrix}0 & 0 &0 &0\\1/2&0&1/2 &0\\0&1/2&1/2&0\\0&0&1/2&1/2\end{bmatrix}$$

I also defined $$x_0$$ as the state of the sequence at flip 0. $$x_n = x_{n-1}*P_{ij}$$ is the state at flip n.

$$x_0 = \begin{bmatrix}0 & 0 &0 & 1\end{bmatrix}$$

I defined $$E[X]$$ = $$\sum_{k=0}^{\infty} k*P(State\ 0 \ or \ HTT \ formed \ at \ flip \ k) = k * x_k(j = 0)$$

I am not getting the right answer for some reason. I know there is another way to solve this problem using martingales, but I would like if someone could point out what errors I am making in my process.

• ted.com/talks/peter_donnelly_shows_how_stats_fool_juries . See any paper on Penny's paradox. – David G. Stork Oct 23 '18 at 17:02
• It's bad practice (to say the least) to use the same variable as a dummy variable for a sum (or an integral) and for a real variable attached to the problem. – lulu Oct 23 '18 at 17:04

## 1 Answer

There are four states of interest, according to how much of $$HTT$$ is complete. Thus we have the states $$\emptyset, H,HT,HTT$$. Of course, the expectation from $$HTT$$ is $$0$$.

Let $$E_S$$ be the expectation from a given state $$S$$, and let the answer you want be denoted by $$E=E_{\emptyset}$$.

Barring arithmetic error (always possible) we see that $$E_{HT}=\frac 12\times 1 + \frac 12\times (E_H+1)$$

$$E_H=\frac 12\times (E_{HT}+1)+\frac 12\times (E_H+1)$$

Together these imply that $$E_H=6\quad \&\quad E_{HT}=4$$

Now we also have $$E=\frac 12\times (E_H+1)+\frac 12\times (E+1)\implies E=8$$

• 8 is the same answer I got, which was wrong – Kevin Oct 23 '18 at 17:32
• well, my methodology should be correct, though the computation is a little error prone. What answer do you believe to be correct? – lulu Oct 23 '18 at 17:34
• I believe the answer is 18 – Kevin Oct 23 '18 at 17:35
• I simulated it and got an average of $8.01$. It very seldom takes as long as $18$, so that answer is surely wrong. I don't see anything to contradict $8$ as the answer. – lulu Oct 23 '18 at 17:41
• $8$ is correct, the string $HTT$ has no proper initial segments which are equal to final segments, in which case the expected waiting time is just $2^n$ where $n$ is the length of the string. – Ned Oct 23 '18 at 18:13