A pattern waiting time is the number of observations required until a specified finite pattern first occurs in a stochastic process. Overlaps between possible occurrences affect the answer; treating sliding windows as independent generally gives the wrong mean.
For independent fair coin tosses, let be the expected additional tosses to first see HH with no current matching prefix, and the expectation after one H. Then and , giving . For HT, the analogous equations give four. The patterns have the same probability in a fixed two-toss window, but different self-overlap structure.
Here is a finite word over an alphabet, every letter of the word has positive probability, and is the set of lengths of its borders of a word, including its full length. Start a unit-capital gambler before every draw, betting successively on the word's letters and dividing surviving capital by the required letter probability. Total capital minus the number of entrants is a martingale. At the first full match, the surviving gamblers correspond exactly to the borders, giving the displayed formula by optional stopping. Disjoint blocks of full word length give a geometric tail bound from a uniform escape probability, so the waiting time is integrable; bounded word length and positive letter probabilities give bounded martingale increments and justify stopping.

Articles by others on the same topic (0)

There are currently no matching articles.