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?

  • $\begingroup$ For a fixed position XXXX within the sequence you could explain it in terms of waiting times. $\endgroup$ – user17794 May 29 '12 at 19:03
  • 4
    $\begingroup$ Let's say you got three heads in a row, and the next one was tails. Then you always need four more tosses, minimum, to get HHHH. On the other hand, if you started with HTHH, you have failed to get HTHT, but you have a chance of getting the pattern HTHT in three more tosses, because the last H can be the beginning of the new pattern. Basically, failure always forces you to completely reset in the HHHH case, whereas sometimes you don't have to with HTHT. $\endgroup$ – Thomas Andrews May 29 '12 at 19:34

The other answers are perfectly good, but I feel a picture is worth a thousand words in this case.

enter image description here

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.

  • $\begingroup$ Thanks for the picture. When analyzing this in my stochastic methods class, the prof calculated the lower chain's expectation by saying "it takes an expected four flips to reach the ..HT state, and then from there another 12 flips to reach HTHT". Do you understand why we focus on these states "go directly to jail" states when calculating the expectation? $\endgroup$ – Fixee May 29 '12 at 22:57
  • 1
    $\begingroup$ Hell if I know. I'm just a guy who likes to draw pictures. ;) $\endgroup$ – Rahul May 29 '12 at 23:01

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$.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.