The probability of a word appearing in a sequence of n letters drawn at random from a finite alphabet 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.
 A: 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$.
A: Let $a_k$ be the probability that the word appears in the first $k$ letters. We have $a_0=a_1= \dots =a_{r-1}=0$.
Either $w$ appears in the first $n-1$ letters chosen, or it appears for the first time at the $n^{th}$ digit. In this second case (excluding the case of overlaps - see below) the final $r$ digits are determined - probability $a^{-r}$. The word cannot appear in the first $n-r$ digits. In simple cases therefore we have $$p_n=p_{n-1}+a^{-r}(1-p_{n-r})$$.

As an interlude, it is not always that simple. The word ONION taken from an alphabet of $26$ capital letters can appear overlapping $ONIONION$ - here two letters overlap and we have to exclude the word from the first $n-3$ letters and not just the first $n-5$ if we are to avoid double-counting. This case requires minor adjustments.

We are left, then, with a simple recurrence, which is not homogeneous, but it is easy to see that $p_k=1$ is a particular solution.
The homogeneous equation is of the form $$p_n-p_{n-1}+a^{-r}p_{n-r}=0$$ and the auxiliary equation is $$x^r-x^{r-1}+a^{-r}=0$$
This can be solved using the usual methods for such equations.
The following is very sketchy.
The function $f(x)=x^r-x^{r-1}+a^{-r}$ has a local minimum at $x=1-\frac 1r$ and therefore the root with largest absolute value lies in the range $1-\frac 1r \lt \alpha \lt 1$. This will dominate the asymptotics which should be of the form $a_n=1-A\alpha^n$, with the probability tending to $1$ and $n$ increases.
Since $f(x)$ is a perturbation of $x^r-x^{r-1}$ we would expect one root near $x=1$ and other roots to have small absolute value (certainly for $a$ and $r$ reasonably large), so the asymptotics should give a good estimate.
A: Well, the possible number of words of length n using a characters is $a^n$
On the other side, the odds of w showing up is the different ways you can choose r consecutive positions in a string of n positions, which is (if I'm not mistaken) $n-r+1$, 
So the odds are $$\frac {n-r+1}{a^n}$$
Edit: I'll try to fix this later since it's obviously wrong and I'll be counting multiple cases if I fix it now
