HH vs. THTH Coin Toss

Question

Alice tosses a fair coin until either she or Bob wins. Alice wins if she gets two consecutive heads (HH) and Bob wins if he gets Tails and Heads twice in a row (THTH). What is the probability that Bob wins the game?

Attempt: If the first toss is T, there will certainly be a TH before HH. If the first toss is H, the only way to get HH before TH is if the second toss is also H. Thus, the probability of getting TH before HH is 3/4. Given any sequence with TH before HH, there are three possibilities for the tosses following that TH:

1. H, in which case Alice wins
2. TT, in which case Alice will keep tossing
3. TH, in which case Bob wins.

Hence, the probability that Bob wins must be greater than 3/4 * 1/4 = 3/16. But what is the exact probability? Thanks in advance!

Answer 1

Your work almost gets there.

Let's suppose $b$ is the probability that Bob wins given that nobody has won yet and the last two tosses were $TH$. If the next two are $TT$ then neither wins immediately and eventually there will be another $H$ bringing the game back to $TH$. So you have said in effect that $$b= \frac12\times 0 + \frac14 \times b +\frac14 \times 1$$ which has the solution $b=\dfrac13$.

But you also said Alice could have won at the start too with $HH$ before the first $T$ with probability $\dfrac14$, so overall the probability Bob wins is $$\frac14\times 0+\frac34 \times b = \frac14.$$

Answer 2

A turn-the-crank approach to solve such problems is to represent them as Markov chains and use repeated matrix-vector multiplication to determine the limiting distribution.

In this case, we make a Markov chain with states $$\{\text{Init},H,HH,T,TH,THT,THTH\}.$$ $\text{Init}$ corresponds to the start of the game, before any coin flips have occurred. The remaining states correspond to a "longest suffix match" on the sequence of observed coin flips thus far. For example, if the observed sequence is $HTTHT$, the game is in state $THT$.

The transition graph is given by

The transition matrix $P$ is obtained by converting the graph into a matrix. Each edge has a probability of $\frac{1}{2}$ except for the two edges associated to the absorbing states $HH$ and $THTH$, which have probability $1$.

Lastly, let $v=(1,0,\ldots,0)^\intercal$ be the initial state distribution. The limiting distribution is $$ v_\infty=\lim_{n\rightarrow\infty}v^{\intercal}P^{n}. $$ It is easy to see that $v_\infty$ is all zeros except for the two coordinates corresponding to the absorbing state (the game terminates almost surely). The answer is the entry of $v_\infty$ corresponding to $THTH$.

Here is some Python code:

import numpy as np

TRANS_MAT = np.array([
    # Init    H   HH    T   TH  THT  THTH
    [  0.0, 0.5, 0.0, 0.5, 0.0, 0.0,  0.0],  # Init
    [  0.0, 0.0, 0.5, 0.5, 0.0, 0.0,  0.0],  # H
    [  0.0, 0.0, 1.0, 0.0, 0.0, 0.0,  0.0],  # HH
    [  0.0, 0.0, 0.0, 0.5, 0.5, 0.0,  0.0],  # T
    [  0.0, 0.0, 0.5, 0.0, 0.0, 0.5,  0.0],  # TH
    [  0.0, 0.0, 0.0, 0.5, 0.0, 0.0,  0.5],  # THT
    [  0.0, 0.0, 0.0, 0.0, 0.0, 0.0,  1.0],  # THTH
])
INIT_DIST = np.array([1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0])

eigvals, eigvecs = np.linalg.eig(TRANS_MAT)

# Compute the limit of eigvals**n as n goes to infinity.
n_iters = 0
prev = np.nan
limit_eigvals = eigvals
while True:
    prev, limit_eigvals = limit_eigvals, limit_eigvals * limit_eigvals
    n_iters += 1
    if np.max(np.abs(limit_eigvals - prev)) < 1e-12:
        break

# Compute the limiting distribution.
# Equivalent to INIT_DIST @ eigvecs @ limit_eigvals @ inv(eigvecs).
limit_dist = np.linalg.solve(
    eigvecs.T, INIT_DIST @ (eigvecs * limit_eigvals))

prob_alice_wins = np.real(limit_dist[2])