# 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.

• You might be interested in section 1.4, "Words and Regular Languages" in "Analytic Combinatorics" by Flajolet and Sedgewick. The book can be found online in pdf form. – awkward Dec 4 '17 at 14:51
• @awkward Thank you, that is helpful. – Mark Bennet Dec 4 '17 at 15:33

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$.

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.

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

• Let me know if there's something you don't get or think it's wrong – Francisco José Letterio Dec 4 '17 at 17:25
• Wait I'm forgetting something, lemme edit – Francisco José Letterio Dec 4 '17 at 17:31