combinatoricsexpected valueprobabilitystatistics
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 probability that player A wins is $\frac{3}{4}$, by the following logic. Suppose it takes more than three throws for player B to win; then all earlier throws must have been $T$'s, because if there's even a single $H$ before the sequence $TTH$, player A would win. Thus player B only wins with the sequences $TTH, TTTH, TTTTH$, etc, and those probabilities add to $\frac{1}{4}$.
Let $x$ be the number of expected flips to get $HTT$; also, let $y$ be the number of additional flips after flipping an $H$, and $z$ be the number of additional flips after flipping an $HT$.
If the first flip is an $H$, then the expected number of additional flips required is $y$; if the first flip is a $T$, then the expected number of additional flips is $x$. This yields the equation $x = 1 + \frac{1}{2}y + \frac{1}{2}x$.
Similarly, after flipping an $H$, if the next flip is also an $H$, then the expected number of additional flips required is $y$, whereas if the next flip is a $T$, the expected number of additional flips required is $z$.This yields the equation $y = 1 + \frac{1}{2}y + \frac{1}{2}z$.
Finally, after flipping $HT$, if the next flip is an $H$, the expected number of additional flips required is $y$, whereas if the next flip is a $T$, we are done.This yields the equation $z = 1 + \frac{1}{2}y$.
Simplifying, we get the system
$$\begin{align} x &= y + 2 \\ y &= z + 2 \\ 2z &= y + 2 \end{align}$$
which yields $(x,y,z) = (8,6,4)$.
Thus the expected number of flips for player A to win is $8$.
Edit:* Yes, the probability can be computed for a general pattern. See below the figure.
Intuitive explanation of winning edge:
Given the other player picks any pattern, say HHH, the player who goes second can pick a pattern which has the beginning of the opponents' pattern as a suffix.
So the second player would fix THH in this case. This means that except for the case that HHH occurs as the first 3 tosses, he can win.
More generally, given an arbitrary pattern, say $X_1,\ldots,X_n$ pick a pattern of the form $A, X_1,\ldots,X_{n-1}.$
By doing this, the first player is forcing the other player to typically win at a depth one more than herself, except if their pattern occurs in the beginning.
Here is a pictorial illustration of another example showing the depth of winning states. The first player (opponent) picks HTH and the second player (you) pick HHT.
There is a neat way of computing the winning probability in this Penney-Ante game which was first mentioned by John H. Conway.
Given two $q-$ary words (from a finite alphabet of $q$ letters) $X=(x_1,\ldots,x_n)$ and $Y=(y_1,\ldots,y_m),$ define the correlation of $X$ and $Y$ as $$ C[X,Y;z]=\sum_{i=0}^{n-1} f(n-i) z^i, $$ where $f(i)=1$ if and only if the partial word $(x_i,\ldots,x_n)$ is a prefix of the word $(y_1,\ldots,y_m),$ otherwise $f(i)=0.$ In general, $[X,Y]\neq [Y,X].$ Then the odds that word $Y$ beats word $X$ in this game is given by the expression $$ \frac{C[X,X;q]-C[X,Y;q]}{C[Y,Y;q]-C[Y,X;q]}, $$ though the proof was not given by Conway and was supplied much later by Guibas and Odlyzko.
Note that if the odds are $o$ the probability of winning is $$o/(1+o).$$
Best Answer
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$$