Coin Toss Sequence: HTT
How many times do you expect to toss a coin to get a sequence Heads Tails Tails (HTT)?
Answer
This is a markov chain problem. You solve it by recognising when you're in states you'd visited before, and solving a system of equations. Easiest way to solve it is to draw a tree diagram with possible outcomes. You can stop branching the three when you encounter a state you've visited before, or when you reach HTT.
Looking at the image below, we start off with state $S_0$ - before tossing any coins, we have 0 of the required 3-letter sequence. If you toss T, you still don't have the first of the HTT sequence (since we need H to start), so we are back to $S_0$ and we don't branch the tree further in this direction. If you get H, you are in $S_1$ - you've obtained the first of the HTT sequence. If after that you have another H, you haven't progressed but you also haven't ruined your progress so far: your first H becomes uselles and the last one is potentially first of the HTT sequence, so you stay in $S_1$. If you got T, you now have first two of the HTT sequence ($S_2$) - note we haven't seen $S_2$ yet, so we must keep branching until we either get HTT or are back at a familiar state. If the next flip is T, we win; and otherwise we are back at $S_1$ (as after HTH we can use the last H as start of the new sequence). Now since this is a fair coin, each branch occurs with probability $\frac{1}{2}$.
Lastly, we set up the equations and solve. Denote $E_i$ the expected number of flips needed to get HTT starting from state $S_i$. Then: $$E_0=1 + \frac{1}{2}\cdot E_0 + \frac{1}{2} \cdot E_1$$ $$E_1 = 1 + \frac{1}{2}\cdot E_1 + \frac{1}{2}\cdot E_2$$ and $$E_2 = 1 + \frac{1}{2}\cdot E_1 + \frac{1}{2}\cdot 0$$.
Solving the system of three equations for $E_0$, we get $E_0=8$.