= Waiting time for a word in independent nonuniform symbols
{title2=$\mathbb E\tau_w=\sum_{k\in B(w)}\bigl(\prod_{j=1}^k p(w_j)\bigr)^{-1}$}
Here $w$ is a finite <word over an alphabet>, every letter of the word has positive probability, and $B(w)$ 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.
Back to article page
