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.

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.