Pattern Waiting Time
You toss a fair coin repeatedly and wait for a specific pattern to appear as a consecutive run. Start with the pattern $\text{HTH}$.
- Model the process as a Markov chain where each state represents the length of the longest suffix of your flip history that matches a prefix of $\text{HTH}$. Write down the transition matrix, set up the first-step equations for the expected waiting time $E[T]$, and solve for $E[T]$.
- Now generalize. For an arbitrary binary pattern $P = p_1 p_2 \cdots p_L$ with a fair coin, explain how to construct the corresponding automaton (with states $0, 1, \ldots, L$), and derive a closed-form formula for $E[T]$ in terms of the pattern's self-overlap structure.
Hints
- Track how much of the target pattern you have matched so far -- this gives you a natural set of states for a Markov chain.
- The failure transitions (what happens when you do not extend your current match) follow the same logic as the KMP failure function: look for the longest suffix of your current match that is also a prefix of the target.
- For the general formula, notice that each self-overlap of length $k$ (where the last $k$ characters of $P$ equal the first $k$) contributes $2^k$ to the expected waiting time. Sum over all such $k$.
Worked Solution
How to Think About It: This is a classic Markov chain problem. You track how much of your target pattern you have "built up" so far. Each coin flip either extends your current match by one character or knocks you back to some earlier state. The trick is figuring out the failure transitions -- when you fail to extend, you do not always go back to state 0, because the tail of what you have already seen might itself be a prefix of the target. This is the same failure-function logic as the KMP string matching algorithm. Once you have the chain, it is a standard first-step expected-value calculation. Before doing any algebra, you can guess: the pattern HTH has a self-overlap (it starts and ends with H), which creates a "false start" effect that inflates the waiting time compared to a non-overlapping pattern like HTT.
Quick Estimate: A pattern of length 3 on a fair coin has a base waiting time of at least $2^3 = 8$ flips (that is the contribution from the full pattern match). The overlap where the last character H matches the first character H adds $2^1 = 2$ more, giving roughly $8 + 2 = 10$. Compare this to HTT, which has no self-overlap beyond the trivial full match, so $E[T_{\text{HTT}}] = 8$. The overlap penalty for HTH is modest but real.
Approach: Build the Markov chain for HTH, write first-step equations, and solve.
Formal Solution:
*Part (i): The HTH chain*
The states are $\{0, 1, 2, 3\}$, where state $k$ means the last $k$ flips match the first $k$ characters of HTH, and state 3 is absorbing (pattern found).
Transitions (each outcome has probability $1/2$):
- State 0 (no match): Flip H $\to$ state 1 (matched "H"). Flip T $\to$ state 0.
- State 1 (matched "H"): Flip T $\to$ state 2 (matched "HT"). Flip H $\to$ state 1 (the new H is itself a valid prefix).
- State 2 (matched "HT"): Flip H $\to$ state 3 (matched "HTH" -- done!). Flip T $\to$ state 0 ("HTT" has no prefix overlap with HTH).
- State 3: Absorbing.
Let $E_i$ be the expected number of additional flips from state $i$ to reach state 3.
$$E_0 = 1 + \frac{1}{2} E_1 + \frac{1}{2} E_0$$
$$E_1 = 1 + \frac{1}{2} E_1 + \frac{1}{2} E_2$$
$$E_2 = 1 + \frac{1}{2}(0) + \frac{1}{2} E_0$$
From the first equation: $\frac{1}{2} E_0 = 1 + \frac{1}{2} E_1$, so $E_0 = 2 + E_1$.
From the second: $\frac{1}{2} E_1 = 1 + \frac{1}{2} E_2$, so $E_1 = 2 + E_2$.
From the third: $E_2 = 1 + \frac{1}{2} E_0$.
Substituting backward:
$$E_1 = 2 + 1 + \frac{1}{2} E_0 = 3 + \frac{1}{2} E_0$$
$$E_0 = 2 + 3 + \frac{1}{2} E_0 = 5 + \frac{1}{2} E_0$$
$$\frac{1}{2} E_0 = 5 \implies E_0 = 10$$
So $E_1 = 8$ and $E_2 = 6$.
$$\boxed{E[T] = E_0 = 10}$$
*Part (ii): General binary pattern*
For an arbitrary pattern $P = p_1 p_2 \cdots p_L$ on a fair coin, construct the automaton exactly as above: state $k$ means the last $k$ flips match $p_1 \cdots p_k$. The failure transitions use the KMP failure function -- when you are in state $k$ and the next flip does not match $p_{k+1}$, you fall back to the longest proper suffix of $p_1 \cdots p_k$ (plus the new flip) that is also a prefix of $P$.
The closed-form result is the Conway leading number formula. Define the self-overlap indicator: for each $k \in \{1, 2, \ldots, L\}$, let $c_k = 1$ if the last $k$ characters of $P$ equal the first $k$ characters of $P$, and $c_k = 0$ otherwise. (Note $c_L = 1$ always, since the whole pattern trivially matches itself.) Then:
$$E[T] = \sum_{k=1}^{L} c_k \cdot 2^k$$
For a biased coin with $P(H) = p$ and $P(T) = 1 - p$, the contribution of each overlapping position $k$ is $\prod_{i=1}^{k} \frac{1}{q_i}$, where $q_i$ is the probability of the $i$-th character in the pattern.
Verification for HTH: The self-overlaps are at $k = 1$ (suffix "H" = prefix "H") and $k = 3$ (trivial). Position $k = 2$: suffix "TH" $\neq$ prefix "HT", so $c_2 = 0$. Therefore $E[T] = 2^1 + 2^3 = 2 + 8 = 10$. This matches.
Comparison examples: - HTT: only $c_3 = 1$, so $E[T] = 2^3 = 8$. - HH: $c_1 = 1$ ("H" = "H") and $c_2 = 1$, so $E[T] = 2 + 4 = 6$. - THH: only $c_3 = 1$, so $E[T] = 8$.
Answer: For the pattern HTH on a fair coin, $E[T] = 10$. In general, $E[T] = \sum_{k=1}^{L} c_k \cdot 2^k$, where $c_k = 1$ if the pattern has a self-overlap of length $k$ (its last $k$ characters equal its first $k$), and $c_k = 0$ otherwise. The automaton is constructed using the KMP failure function: upon a mismatch at state $k$, transition to the longest proper prefix of $p_1 \cdots p_k$ (appended with the new flip) that is also a prefix of $P$.
Intuition
The expected waiting time for a pattern is not just about its length -- it depends on the pattern's internal structure. A pattern that overlaps with itself (like HTH, which starts and ends with H) takes longer to appear than one that does not (like HTT). The reason is restart efficiency: when you are partway through HTT and fail, you have to start completely fresh. But when you are partway through HTH and see the final H, that H could also be the start of a new attempt at HTH -- so partial progress "recycles" and you might think this helps, but it actually creates false starts that waste time. The Conway leading number formula $\sum c_k \cdot 2^k$ encodes exactly this: each self-overlap of length $k$ adds $2^k$ to the expected wait.
This self-overlap structure is identical to what the KMP string-matching algorithm computes with its failure function, so there is a deep connection between pattern-matching automata and expected stopping times. In quant work, this type of analysis shows up whenever you model sequences of events and want to know how long until a specific signal pattern triggers -- for example, waiting for a particular sequence of up/down moves in a price process, or detecting a regime-change pattern in tick data.