Waiting Time for Coin Patterns
See how self-overlap changes the waiting time for an exact coin pattern.
By Riano · Published · Updated · Report a correction
Waiting Time for Coin Patterns
When repeatedly flipping a coin, analyzing the time until a specific sequence of heads (H) and tails (T) first appears is a classic problem in discrete stochastic processes. Unlike the geometric waiting time for a single success, the expected waiting time for a longer pattern is heavily influenced by how the pattern overlaps with itself.
Worked Example: HTH vs HH
Consider tossing a fair coin until the pattern HTH appears. The expected waiting time E[T] can be surprisingly calculated by the "border identity" (or Conway's algorithm), which states that the expected waiting time is the sum of inverse probabilities of the prefix-suffixes (borders) of the pattern.
For the pattern HTH, the valid borders (prefixes that are also suffixes) are:
- Length 3: HTH (probability 1/8) → contributes 8
- Length 1: H (probability 1/2) → contributes 2
Summing these gives an expected waiting time of 10 flips. In contrast, for the pattern HH, the valid borders are HH and H, yielding an expected waiting time of 4 + 2 = 6 flips. Even though HH is shorter and seems easier to get, the overlapping nature of HTH makes it take longer on average to observe.
Interactive Experiment
Use the interactive module to explore how the expected waiting time and the transient probability of hitting the pattern by a given horizon change. You can adjust the coin's bias and see the underlying finite-state automaton that tracks the longest matched prefix at any given step.
- Pattern: Choose different sequences to see how self-overlap affects the waiting time.
- Head probability: See what happens as the coin becomes biased towards heads or tails. Notice how the expected time becomes Infinite if the sequence requires a side that has zero probability.
- Horizon: Adjust the number of flips to see how the transient probability P(T ≤ N) evolves in the trace table over time.
Limitations
The exact computations here are feasible because the patterns are short and the state space of the automaton is small. For extremely long patterns or large alphabets (e.g., matching a word in a book), constructing the full transition matrix and computing matrix powers would require more efficient string matching algorithms (like Aho-Corasick) and optimized sparse matrix techniques. Additionally, the calculations assume perfect independent and identically distributed (IID) coin flips.
References
The mathematical foundation for computing expected waiting times using prefix-suffix self-overlap logic.
Experience it interactively
Adjust parameters, observe in real time, and build deep intuition with Riano’s interactive Waiting Time for Coin Patterns module.
Try Waiting Time for Coin Patterns on Riano →