TITLE: The probability of a word appearing in a sequence of n letters drawn at random from a finite alphabet
QUESTION [1 upvotes]: Suppose we have an alphabet of $a$ letters and a word $w$ of length $r$. What is the probablity that $w$ will appear in a sequence of $n$ letters drawn at random from the given alphabet?
I have posted a general question since there seem to be a few of these questions appearing, and this is intended as a general form of question to which general answers can be given. Anyone who wants to add to what I have written - asymptotic of solutions in more detail, for example, or alternative methods - that would be great.
And are there any good references for this kind of problem.

REPLY [1 votes]: The Goulden-Jackson cluster method gives a simple algorithm to compute the generating function for the number of words that avoid a list of "bad words". (Besides being relevant to your problem, the referenced paper is written in a style that is both insightful and entertaining. I happily admit it's one of my all-time favorite papers.) Your problem is a special case of the method where the list consists of a single word. The main result  is that the generating function $f(z)$ for the number of words avoiding the bad word $w$ of length $r$  is 
$$f(z)=\frac1{1-az-\dfrac{z^r}{1+z^{k_1}+z^{k_2}+\cdots}},$$
where the $k$'s are the lengths of tails of the word $w$ that happen to match its initial segments, if any. Then, the probability that random word of length $n$ includes word $w$ would be $1-[z^n]f(z)/a^n$.
{"set_name": "stack_exchange", "score": 1, "question_id": 2550568}