Looking for intuition behind coin-flipping pattern expectation I was discussing the following problem with my son:
Suppose we start flipping a (fair) coin, and write down the sequence; for example it might come out HTTHTHHTTTTH....  I am interested in the expected number of flips to obtain a given pattern.  For example, it takes an expected 30 flips to get HHHH.  But here's the (somewhat surprising) thing: it takes only 20 expected flips to get HTHT.  
The tempting intuition is to think that any pattern XXXX is equiprobable since, in batches of 4 isolated flips, this is true.  But when we are looking for embedded patterns like this, things change.  My son wanted to know why HTHT was so much more likely to occur before HHHH but I could not articulate any kind of satisfying explanation.  Can you?

Suppose we have 4-slot queue. By state we mean the longest tail of the coin sequence that matches the pattern $XXXX$ from the left. If there no matching, we denote the state as $\varnothing$. For instance, the state of the sequence $$TTTTHTHHTTTHTH,$$ given the pattern $XXXX = HTHT$, is $HTH$ and the state for the pattern $TTTT$ is $\varnothing$.
Now suppose the pattern is $XXXX = HHHH$. If you have $T$ and fail to complete the pattern, the state collapses to $\varnothing$, so that we have to start at the beginning.
But if the pattern is $XXXX = HTHT$ and the previous state is either $H$ or $HTH$, then the state collapses to $H$ even if you fail. Thus we do not have to start at the beginning in this case. This difference allows us to complete the pattern faster, resulting in the short expected time.
