Coin Toss Sequence: HTH
How many times do you expect to toss a coin to get a sequence Heads Tails Heads (HTH)?
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.
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 HTH 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 HTH 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 HTH sequence, so you stay in $S_1$. If you got T, you now have first two of the HTH sequence ($S_2$) - note we haven't seen $S_2$ yet, so we must keep branching until we either get HTH or are back at a familiar state. If the next flip is H, we win; and otherwise we are back at the start (as after HTT we must restart the sequence). Now since this is a fair coin, each branch occurs with probability $\frac{1}{2}$.
Lastly, we set up the equations. Denote $E_i$ the expected number of flips needed to get HTH starting from state $S_i$. Then: $$E_0=1 + \frac{1}{2}\cdot E_0 + \frac{1}{2} \cdot E_1$$
We're saying that expected number of flips needed for HTH when starting off is the one flip we take to get to next state, and then however much is left from the state we end up in (50% chance we end up needing $E_0$ more, and 50% chance we neeed $E_1$ more. Similarly, $E_1 = 1 + \frac{1}{2}\cdot E_1 + \frac{1}{2}\cdot E_2$ and $E_2 = 1 + \frac{1}{2}\cdot 0 + \frac{1}{2}\cdot E_0$.
Solving the system of three equations for $E_0$, we get $E_0=10$.