HH vs. THTH Coin Toss

conditional probabilityprobabilityproblem solvingrecreational-mathematics

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!

Best Answer

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

enter image description here

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])
Related Question