What is the probability that $THTH$ occurs before $HTHH$ in an infinite sequence of coin flips?

Question

What is the probability that $THTH$ occurs before $HTHH$ in an infinite sequence of coin flips?

The expected number of flips until you first see $THTH$ is $6$, while the expected number until you first see $HTHH$ is $10$. Intuitively, I would guess that the probability that $THTH$ occurs before $HTHH$ is $3/4$. Is there a formal argument to compute this probability?

Probabilistic model: We denote by $(X_{n})_{n \geq 1}$ the random variable of coin flips, taking values in $\{H,T\}^{\mathbb{N}}$. We let $t_{THTH}$ be the first time that $THTH$ occurs in the sequence. We have $$ \mathbb{E}[t_{H}] = \frac{1}{2} \mathbb{E}[t_{H} | X_{1} = H] + \frac{1}{2} \mathbb{E}[t_{H} | X_{1} = T] = \frac{1}{2} + \frac{1}{2} (\mathbb{E}[t_{H}] + 1 ). $$

$$ \mathbb{E}[t_{TH}] = \frac{1}{2} \mathbb{E}[t_{TH} | X_{1} = H] + \frac{1}{2} \mathbb{E}[t_{TH} | X_{1} = T] $$

Answer 1

Discern $p,p_{T},p_{H},p_{TH},p_{HT},p_{THT},p_{HTH}\in\left[0,1\right]$ where $p$ denotes the probability that $THTH$ occurs before $HTHH$ and e.g. $p_{TH}$ denotes the probability that $THTH$ occurs before $HTHH$ under the extra condition that we start with $TH$.

Then we have the following equalities:

• $2p=p_{T}+p_{H}$
• $2p_{T}=p_{T}+p_{TH}$
• $2p_{H}=p_{HT}+p_{H}$
• $2p_{TH}=p_{THT}+p_{H}$
• $2p_{HT}=p_{HTH}+p_{T}$
• $2p_{THT}=1+p_{T}$
• $2p_{HTH}=p_{THT}$

(I avoided fractions, but things might become more clear if you divide both sides by $2$)

I find the solutions:

• $p_{THT}=\frac67$
• $p_{HTH}=\frac37$
• $p_{TH}=p_T=\frac57$
• $p_{HT}=p_H=\frac47$

and finally:$$p=\frac9{14}$$

Check me on mistakes, though.

Answer 2

We have states $\{H,T,HT,TH,THT,HTH,THTH,HTHH\}$ which are the prefixes of your strings. We can write down a Markov transition matrix for these states:

$$A = \frac{1}{2} \begin{pmatrix} 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0\\ 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 & 0 & 0 & 2 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 \end{pmatrix}$$

This is an absorbing Markov chain already in canonical form \begin{pmatrix}Q&R\\0&I\end{pmatrix} thus we can find its fundamental matrix $N$ with

$$N = (I - Q)^{-1}$$ $$N = \frac{1}{7} \begin{pmatrix} 24 & 20 & 12 & 10 & 8 & 6\\ 16 & 32 & 8 & 16 & 10 & 4\\ 10 & 20 & 12 & 10 & 8 & 6\\ 16 & 18 & 8 & 16 & 10 & 4\\ 8 & 16 & 4 & 8 & 12 & 2\\ 4 & 8 & 2 & 4 & 6 & 8 \end{pmatrix}.$$

Finally we can get the probabilities of our absorbing states given an initial probability vector of non-absorbing states $\vec p$with ${\vec p}^TNR$. Assuming we threw one coin already our initial state is $[1/2, 1/2, 0, 0, 0, 0]^T$, and thus our final answer is that we end up with $THTH$ $9/14$th of the time and $HTHH$ $5/14$th of the time.