Toss It Til You're Convinced!

Let $n$ be the number of heads already obtained, and $E_n$ the expected number of tosses needed to toss three heads in a row. Obviously, $E_3 = 0$ , and the problem asks for $E_0$ . In general, $E_n = 1 + \sum_k p_{n\to k} E_k,$ where $p_{n\to k}$ is the probability of getting from state $n$ to state $k$ . For this coin, $p_{n\to 0} = 1/3$ (tossing "tail" gets you back to state zero), and $p_{n\to n+1} = 2/3$ (tossing "head" gets you one step ahead). Thus $\begin{cases} E_0 = \frac13 E_0 + \frac23 E_1 + 1; \\ E_1 = \frac13 E_0 + \frac23 E_2 + 1; \\E_2 = \frac13 E_0 + 1. \end{cases}$ Multiplying each equation by 3 and writing it in matrix notation, we get $\left[\begin{array}{ccc} 2 & -2 & 0 \\ -1 & 3 & -2 \\ -1 & 0 & 3 \end{array}\right]\ \left[\begin{array}{c} E_0 \\ E_1 \\ E_2\end{array}\right] = \left[\begin{array}{c} 3 \\ 3 \\ 3 \end{array}\right].$ The solution is $\left[\begin{array}{c} E_0 \\ E_1 \\ E_2\end{array}\right] = \frac18 \left[\begin{array}{ccc} 9 & 6 & 4 \\ 5 & 6 & 4 \\ 3 & 2 & 4 \end{array}\right]\ \left[\begin{array}{c} 3 \\ 3 \\ 3 \end{array}\right] = \left[\begin{array}{c} 57/8 \\ 45/8 \\ 27/8 \end{array}\right],$ showing that the expected number of tosses is $E_0 = \boxed{57/8}$ , so that we submit the answer 65 .

You initially have a $1/3$ probability of getting a tail, in which case you're back where you started, but you've "spent a move"

You have a $(2/3)*(1/3) = 2/9$ chance of getting a head, but then a tail, in which case you are back where you are started, but you have "spent $2$ moves".

You have a $(2/3)*(2/3)*(1/3) = 4/27$ chance of getting a head and then another head and then a tail. In which case end up where you started but have spent ( $3$ moves).

Finally, you have a $(2/3)*(2/3)*(2/3)$ ) chance of getting heads, heads, heads, in which case you are done, and you did $3$ flips, which adds on $(2/3)*(2/3)*(2/3)*3$ to the expectaion value.

This translates to the following equation for $E$ :

$E(HHH) = (1/3)(E+1)+(2/9)(E+2)+(4/27)(E+3) +24/27$

Solving that linear equation, $E(HHH) = 57/8$ .

$57+8 = \boxed{65}$