Coin sequence paradox from Martin Gardner's book

"An event less frequent in the long run is likely to happen before a more frequent event!"

How can I show that THTH is more likely to turn up before HTHH with a probability of

9/14, even though waiting time of THTH is 20 and HTHH, 18!

I would be very thankful if you could show me the way of

calculating the probability of turning up earlier,

and the waiting time. Thank you!

Imagine that as you flip the coin, you keep track of your current progress towards getting THTH and your current progress towards getting HTHH. You can do this with a pair of numbers in the range $0$ through $4$: the first number tells you how many consecutive letters of THTH you currently have, and the second does the same for HTHH. For example, suppose that you start out with THHTHTT; after the first T, you’re one step towards THTH, and you’ve made no progress towards HTHH, so your present status is $\langle 1,0\rangle$. Then you get an H, so you’re two steps of the way towards THTH and one towards HTHH, so your status is $\langle 2,1\rangle$. In this sequence of seven tosses you don’t complete either sequence, though you get three steps out of four on each of them, and after these seven tosses you are in effect starting over from scratch, as you can see in the following table:

$$\begin{array}{r|c} \bf{Tosses:}&&\bf T&\bf H&\bf H&\bf T&\bf H&\bf T&\bf T\\ \hline \bf{THTH:}&0&1&2&0&1&2&3&1\\ \bf{HTHH:}&0&0&1&1&2&3&2&0 \end{array}$$

The question is how likely you are to get $4$ in the top line before you get $4$ in the bottom line.

What states are possible? It’s not too hard to check that the only possible states besides those already seen in the table are $\langle 4,3\rangle$, when THTH appears first, and $\langle 0,4\rangle$, when HTHH appears first. For each of the seven non-terminal states $\langle m,n\rangle$, let $p_{m,n}$ be the probability that THTH appears before HTHH; we’re interested specifically in $p_{0,0}$.

If we’re in state $\langle 0,0\rangle$, with probability $\frac12$ we’ll toss H and find ourselves in state $\langle 0,1\rangle$, and with probability $\frac12$ we’ll toss T and be in state $\langle 1,0\rangle$, so it must be that $$p_{0,0}=\frac12p_{0,1}+\frac12p_{1,0}\;.$$ If we’re in state $\langle 0,1\rangle$, with probability $\frac12$ we get H, putting us back in state $\langle 0,1\rangle$, and with probability $\frac12$ we get T, putting us in state $\langle 1,2\rangle$, so $$p_{1,0}=\frac12p_{0,0}+\frac12p_{1,2}\;.$$ Continuing this analysis, and multiplying each of the equations by $2$ to clear the fractions, we find ourselves with the system:

$$\begin{cases} 2p_{0,0}=p_{0,1}+p_{1,0}\\ 2p_{0,1}=p_{0,1}+p_{1,2}\\ 2p_{1,0}=p_{2,1}+p_{1,0}\\ 2p_{1,2}=p_{2,3}+p_{1,0}\\ 2p_{2,1}=p_{0,1}+p_{3,2}\\ 2p_{2,3}=p_{0,4}+p_{3,2}=p_{3,2}\\ 2p_{3,2}=p_{4,3}+p_{0,0}=1+p_{1,0}\;, \end{cases}$$

since $p_{0,4}=0$ and $p_{4,3}=1$. From the second and third equations we have $p_{0,1}=p_{1,2}$ and $p_{1,0}=p_{2,1}$, and from the sixth $p_{3,2}=2p_{2,3}$, so we can rewrite the system as

$$\begin{cases} 2p_{0,0}=p_{1,2}+p_{2,1}\\ 2p_{1,2}=p_{2,3}+p_{2,1}\\ 2p_{2,1}=p_{1,2}+2p_{2,3}\\ 4p_{2,3}=1+p_{2,1}\;, \end{cases}$$

which after some slightly tedious work yields the solution $p_{0,0}=\dfrac9{14}$, as desired.

There are slicker ways, but this is about as elementary an approach as I can offer.

From an intuitive point of view it’s not hard to see why we should be likely to hit THTH before HTHH. In order to hit HTHH, I have to get HTH. Ignoring the beginning of the game, half of the time that HTH is immediately preceded by a T, and I’ve already finished with THTH. The other half of the time, the HTH is preceded by H, and I’ve a 50% chance of getting the H needed to complete HTHH. But I’ve also a 50% chance of getting a T, leaving me with HTHT, and then a 50% chance of getting an H to finish a THTH. In other words, from a non-terminal HTH I’ve a 25% chance of tossing TH$ and finishing with THTH. In other words, given that I’ve just tossed HTH, which I must do in order to finish with HTHH, there’s a 50% chance that it completes a THTH, and the other half of the time there’s a 25% chance that I’ll continue with TH and end up with THTH. Thus, the probability that I end with THTH given that I’ve just tossed HTH is at least $\frac12+\frac12\cdot\frac14=\frac58$.

Here is a both nontrivial and advanced solution.

Consider an ideal gambling where a dealer Alice tosses a fair coin repeatedly. After she made her $(n-1)$-th toss (or just at the beginning of the game if $n = 1$), the $n$-th player Bob joins the game. He bets $2^0\$$ that the $n$-th coin is $T$. If he loses, he leaves the game. Otherwise he wins $2^1\$$, which he bets that the $(n+1)$-th coin is $H$. If he loses, he leaves the game. Otherwise he wins $2^2\$$, which he bets that the $(n+2)$-th coin is $T$. This goes on until he wins $2^4\$$ for $THTH$ and leaves the game, or the game stops.

Thus let $X^{(n)}_k$ be the r.v. of the winning the $n$-th player made when $k$-th coin toss is made. If we let

$$X_n = X^{(1)}_n + \cdots + X^{(n)}_n,$$

Then it is easy to see that $X_n - n$ is a martingale null at 0. Thus if $S$ denotes the stopping time of the first occurrence of $THTH$, and if we assume that $\mathbb{E}[S] < \infty$, then

$$0 = \mathbb{E}[X_{S} - S],$$

thus we have

$$\mathbb{E}[S] = \mathbb{E}[X_{S}] = 2^4 + 2^2 = 20.$$

Let $Y_n$ be the total winning corresponding to $HTHH$, and $T$ be the stopping time of the first occurrence of $HTHH$. Then we have

$$\mathbb{E}[T] = \mathbb{E}[Y_{T}] = 2^4 + 2^1 = 18.$$

Finally, let $U = S \wedge T$ be the minimum of $S$ and $T$. Then it is also a stopping time. Now let $p = \mathbb{P}(S < T)$ be the probability that $THTH$ precedes $HTHH$. Then

$$ \mathbb{E}[U] = \mathbb{E}[X_{U}] = \mathbb{E}[X_{S}\mathbf{1}_{\{S < T\}}] + \mathbb{E}[X_{T}\mathbf{1}_{\{S > T\}}] = 20p + 0(1-p),$$

and likewise

$$ \mathbb{E}[U] = \mathbb{E}[Y_{U}] = \mathbb{E}[Y_{S}\mathbf{1}_{\{S < T\}}] + \mathbb{E}[Y_{T}\mathbf{1}_{\{S > T\}}] = (2^3 + 2^1)p + 18(1-p).$$

Therefore we have $p = 9/14 \approx 64.2857 \%$.

It is enough to devise a set of linear equations ($p=q=1/2$): \begin{align*} T &= pT+qTH \\ TH &= pTHT + qH \\ THT &= pT+q1 \\ H &= p(pT+q(pTHT+q0))+qH \\ X &= pT + qH \end{align*}

and after solving it

\begin{align*} T &= 5/7 \\ TH &= 5/7 \\ THT &= 6/7 \\ H &= 4/7 \\ X &= 9/14 \end{align*}

We get $X = 9/14$ which is what were you looking for. Let (1) means getting THTH before HTHH. What those equations mean is that probability of (1) starting from T is the same as $1/2$ of probability of (1) starting from TT (which is equivalent to T) and $1/2$ of probability of (1) starting from TH (which is not equivalent). The rest follows similar suit.

Edit: To be more intuitive (but less strict) let us observe that if HTHH happens at position other than 0 (and that happens with $1-1/16 = 15/16$ probability), then with probability at least $1/2$ THTH happens before -- due to probability of T before HTHH. Just by that you know that probability of (1) is greater than $15/16 \cdot 1/2 = 15/32$. Adding probability of THTHT (the last T is required so the events won't overlap) at position 0 (1/32) you got 1/2 total and we haven't counted all the instances yet, so surely probability of (1) is strictly greater than 1/2.

Hope that helps ;-)