Waiting time for a word in independent uniform symbols
= Waiting time for a word in independent uniform symbols
Let a fixed word $w$ be sampled from an alphabet of $q$ symbols by independent uniform draws, and let $\tau_w$ count draws through its first occurrence. If $B(w)$ is the set of lengths of the <borders of a word>, including the full length, then
$$
\mathbb E\tau_w=\sum_{k\in B(w)}q^k.
$$
Shorter borders contribute because a failed or completed match can retain a suffix that is already a prefix of the next match.