# What is expected number of throws in the Penney's game?

Two players toss a coin until HTT and the first player wins or TTH and the second player wins. What is the expected number of throws in the game?

My ideas: I tried to make a table with probabilities that game finishes after 3, 4 and so on tosses. Unfortunately, the Expected sum diverges in my case.

• The expected sum should not diverge, as the expected number of turns for each is $8$ and so the expected number for one to win should be no greater. Oct 8, 2020 at 14:51

Let $$x_{TH}$$ be the expected number of remaining throws, given that $$TH$$ are the last two coins (and that no one has yet won). And same for the other alternatives.

Then we can write the system of recursions

\begin{align} x_{TH}&=1 + \frac{1}{2}x_{HT} + \frac{1}{2}x_{HH}\\ x_{TT}&=1 + \frac{1}{2}x_{TT}\\ x_{HH}&=1+\frac{1}{2}x_{HT} + \frac{1}{2}x_{HH}\\ x_{HT}&=1+ \frac{1}{2}x_{TH}\\ \end{align}

The second equation implies $$x_{TT}=2$$. The rest are solved by $$x_{TH}=x_{HH}=6$$ , $$x_{HT}=4$$.

Then the expected number of throws after the first two throws is $$\frac{1}{4}(2+ 6 +6 +4)=9/2$$

and the total expected number of throws is $$2+\frac92=\frac{13}{2}=6.5$$

• Yes. I would do essentially this, though perhaps writing the equations as $x_{TH}=1+\frac12 x_{HH}+\frac12 x_{HT}$ and $x_{TT}=1+\frac12 0+\frac12 x_{TT}$ etc. Oct 8, 2020 at 15:40
• @Henry You're right, it looks better, changed, thanks Oct 8, 2020 at 17:22
• @leonbloy could you please explain why we add 1 to each $x$? Oct 10, 2020 at 15:11
• @student Because we need to throw one more coin in any case. Take for example $x_{TT}$ We have two possible scenarios, each with prob $1/2$. One: we throw a coin and get $T$ - so we have one coin plus the expected number of throws after getting $TT$ - Two: we throw a coin and get $T$ (then we're done, in that case we only need 1 throw . Then $x_{TT}= \frac12 (1 + x_{TT}) + \frac12 (1 + 0) = 1 + \frac12 x_{TT}$ Oct 10, 2020 at 15:36