Katkat
Back

Expected Tosses Until HHT Given HHT Appears Before HTH

DRWQuantitative Researcher · Onsite
HardQuantitative ResearcherOnsiteStatistics & Math

Last updated

Calculate the probability that the coin sequence HHT appears before HTH in repeated fair tosses, and find the conditional expected number of tosses until termination given that HHT appears first.

Problem Statement

A fair coin showing Heads (H) and Tails (T) with equal probability 1/2 is flipped repeatedly and independently. The sequence of flips continues until one of two target patterns appears:

  • Pattern A: HHT
  • Pattern B: HTH

Let T denote the total number of flips until the game stops (i.e., until either HHT or HTH is completed). Let E_A denote the event that Pattern A occurs before Pattern B.

Your tasks are:

  1. Find the probability P(E_A) that HHT appears before HTH.
  2. Compute the conditional expectation E[T | E_A], which is the expected number of flips given that HHT wins the race.

Requirements

  • Set up a discrete-time Markov chain describing the progression toward each pattern, clearly defining the states based on the longest matching prefix.
  • Derive P(E_A) using first-step analysis.
  • Compute E[T | E_A] explicitly using either Doob's h-transform (conditioning the transition matrix on the absorbing event) or first-step analysis on the restricted expectation E[T * 1_{E_A}].
  • Express your final answers as simplified fractions.

Hints

Hint 1

Identify the state space by the longest prefix of either pattern matched so far: empty/T, H, HH, and HT, alongside the absorbing states HHT and HTH.

Hint 2

Use first-step analysis to set up a linear system for the absorption probability p(s) into HHT from each transient state, noting that from HH a win is guaranteed on the next T.

Hint 3

To condition on absorption into HHT, either construct the h-transformed transition probabilities P*(u -> v) = P(u -> v) * p(v) / p(u), or define v(s) = E[T_rem * 1_A | s] and solve for v(start) / p(start).

Follow-up questions

  • What is the unconditional expected number of tosses E[T] until the game stops, and how does E[T | HHT] compare to E[T | HTH]?
  • How would you compute E[T | E_A] using martingale stopping theorems (e.g., Wald's identity or gambling teams) instead of Markov chains?
  • If the coin is biased with P(H) = p != 1/2, for what range of p is HHT more likely to appear before HTH?