Coin Toss Sequence: HHT
How many times do you expect to toss a coin to get a sequence Heads Heads Tails (HHT)?
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 HHT 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 HHT sequence. If after that you have another H, you end up at $S_2$ with first two of the HHT sequence. Otherwise, flipping T on our second flip takes us back to the start, as we can't use the last T as start of the HHT sequence. We continue to branch the tree from $S_2$, as we haven't encountered this state previously. If the next flip is T, we win; and otherwise we are back at $S_2$ (as after HHH we can use the last two as the first two in a new HHT sequence). 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 HHT 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_2 + \frac{1}{2}\cdot E_0$$ and $E_2 = 1 + \frac{1}{2}\cdot 0 + \frac{1}{2}\cdot E_2$.
Solving the system of three equations for $E_0$, we get $E_0=8$.