Bob is playing a computer game. In this game, he flips a fair coin until he flips the sequence: "$HTHHTH$", where $H$ represents a head and $T$ represents a tail. After he flips that sequence, the game ends and Bob wins. Bob has bad memory, so although he knows he has already flipped $5$ coins, he doesn’t remember what they are! Find the expected value of the number of flips Bob still needs to flip until he wins.
Is there a better way to do this without Markov chains?
There is a simple way to solve these kinds of problems via martingales. See chapter 3.1 of https://www.math.upenn.edu/~blockj/bookmain.pdf for a good reference.
The resulting formula is that you look at the lengths of suffixes in the pattern that match the prefix. The sequence starts and ends in H, HTH, and HTHHTH, which have lengths 1, 3, and 6. The answer will then be $$2^6+2^3+2-5=69$$
We subtract 5 since Bob has already flipped 5 coins (with forgotten outcomes), and he will have to flip more coins regardless. Note that it would be more difficult if Bob had flipped more than 6 coins.