Flip a fair coin until three consecutive heads or tails appear

Solution 1:

This can be seen as an MC with 4 states. Denote for convenience $S=\{HHH, TTT\}$

One thing to notice first, is that only before you have tossed any coins at all you need 3 matching tosses till $S$. After that, regardless of the outcome, you have no more than two matching tosses from $S$. Hence we have the following MC:

$S_0$: 3 matching tosses till $S$

$S_1$: 2 matching tosses till $S$

$S_2$: 1 matching tosses till $S$

$S_3$: 0 matching tosses till $S$

Denoting $m_{i,j}$ the mean hitting time of state $j$ starting in state $i$, we obtain the following set of recurrent equations: $$ m_{0,3}=1+m_{1,3}\\ m_{1,3}=1+0.5 m_{1,3} +0.5m_{2,3}\\ m_{2,3}=1+0.5 m_{1,3} +0.5m_{3,3} $$ And the boundary condition is of course $m_{3,3}=0$. Solving this set of equations we get $$ m_{0,3}=1+6=7 $$

Solution 2:

Let $P$ be the expected number when the last two flips match, $Q$ the expected number when the last two flips don't match (or there has only been one flip). Our answer is $Q+1$ as the first flip will take us to state $Q$.
Then $P=\frac 12 \text{(that we match the last 2)}+\frac 12 (Q+1)\text{ (as we are now in state } Q)$ $Q=\frac 12 (1+P)\text{(that we match the last flip)} + \frac 12 (1+Q)\text{(that we don't match the last flip)}$

This gives $P=4, Q=6$ and our final answer is $7$