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?
 A: The other answers are perfectly good, but I feel a picture is worth a thousand words in this case.

When waiting for HHHH, you go directly to jail (do not pass go, do not collect $200) a lot more often than when you are waiting for HTHT.
A: One can explain the ordering of the two mean first hitting times as follows.
The appearance of a word may be modeled through the sequence of the lengthes of the longest prefixes of this word achieved at each time. If the word to reach is U=HHHH then the word W=HTTHTHHTTTTH of your example yields the sequence $(0,1,0,0,1,0,1,2,0,0,0,0,1)$. If the word to reach is V=HTHT then W yields the sequence $(0,1,2,0,1,2,3,1,2,0,0,0,1)$.
In both cases the resulting sequence is a Markov chain on the state space $\{0,1,2,3,4\}$ and one asks for the mean hitting time of state $4$ starting from state $0$. The transition probabilities of the valid transitions are all $\frac12$. The transitions valid in both models are $0\to0$, $0\to1$, $1\to2$, $2\to0$, $2\to3$ and $3\to4$. The transitions valid in model U only are $1\to0$ and $3\to0$. The transitions valid in model  V only are $1\to1$ and $3\to1$.
One can couple the two Markov chains in such a way that they both perform steps $n\to n+1$ simultaneously. Then the position of the V Markov chain is at least as high as the position of the U Markov chain at the same time. Hence the V chain reaches $4$ sooner, in the mean.
Caveat: this coupling does not mean that the V sequence of a given word is always at least as high as the U sequence, only that one can find two processes $(U_n)_n$ and $(V_n)_n$ such that $(U_n)_n$ is distributed like the sequence of the lengthes of the prefixes of U, $(V_n)_n$ is distributed like the sequence of the lengthes of the prefixes of V, and $U_n\geqslant V_n$ almost surely, for every $n$.
A consequence of this simultaneous construction of the hitting times $T_U$ and $T_V$ is that, for every $t$, $\mathrm P(T_U\geqslant t)\leqslant\mathrm P(T_V\geqslant t)$. Hence $\mathrm E(T_V^k)\geqslant\mathrm E(T_U^k)$ for every nonnegative $k$ and, more generally, $\mathrm E(a(T_V))\geqslant\mathrm E(a(T_U))$, for every nondecreasing $a$.
A: 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.
