Waiting time for a word in independent nonuniform symbols
ID: waiting-time-for-a-word-in-independent-nonuniform-symbols
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.
New to topics? Read the docs here!