1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – awkward Dec 4 '17 at 14:51
  • $\begingroup$ @awkward Thank you, that is helpful. $\endgroup$ – Mark Bennet Dec 4 '17 at 15:33
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.