# What is the probability that a sequence of $M$ random letters contains a sub-sequence of $K$ letters?

The alphabet is supposed to have $$n$$ characters (usually $$n=26$$, though in my case $$n=256$$ or $$256^2$$ or $$256^4$$).

Example:

Here $$n=2$$ and the alphabet consists of two letters A and B. The prespecified sub-sequence is ABB (so $$K=3$$). The sequence contains $$M=4$$ letters. The $$M^n$$ possibilities for the sequence are:

AAAA, AAAB, AABA, AABB, ABAA, ABAB, ABBA, ABBB, BAAA, BAAB, BABA, BABB, BBAA, BBAB, BBBA, and BBBB.

The sub-sequence ABB appears (highlighted in bold) 4 times out of 16, and in each of these four cases, it appears only once within the sequence. So the answer is 1/4 in this case. Note that for the sub-sequence AAA, the answer would be 3/16.

In my case, $$M$$ is large (say, $$10^7$$) and $$K$$ is small (say $$K=300$$.) Both the sequence and sub-sequence are random in my case.

• Intuitively, I'd say that the numbers you give mean that for that particular case the probability is so tiny it is effectively zero. For an alphabet of 2 letters, the chance of getting a particular string is independent of what came before - $2^{-300}=4.9x10^{-91}$. For a sequence of only $10^{7}$ letters, this is very unlikely to occur! For 256 letters, the likelihood is an astounding factor smaller. I'd say that if you are more likely to pick the same atom in the universe at random than get this sequence, but maybe someone else can be more specific. Are you doing something with hexadecimal? – Chris Moorhead Apr 12 at 9:35
• For the figures you give ($\ K\approx 300\$, and alphabet size of $\ 2^8, 2^{16}\$ or $\ 2^{24}\$), the chances of your target sequence apperaing anywhere in a randomly generated one, even as long as $\ 10^7\$, are minuscule (effectively zero, in fact). The probability that it will appear starting at any specific point in the generated sequence is $\ 2^{-2400}\approx 10^{-1664}\$ for an alphabet size of $\ 256\$. The expected number of times it should apear in the entire sequence is thus only $\ \left(10^7-300\right)10^{-1664}\approx 10^{-1657}\$. – lonza leggiera Apr 12 at 9:36
• Adding to the comments above, if the $K$-long substring is randomly taken from an alphabet of even $256$ characters, it's pattern will be "enough chaotic" such that the probability of having two (or more) of such substrings overlapping can be considered neglegible wrt the single occurrence. That will allow you to treat the substring as a single letter. – G Cab Apr 12 at 10:19
• Thank you for the comments. Yes, I want the probability in question to be extremely small, say less than $10^{-200}$. I am not interested in its exact value, but an upper bound, close enough to the exact value. I must choose $K$ and $M$ so that the probability is very small. I don't have much of a choice for $n$. This is related to some cryptographic system. I'll tell more if you are interested (the sub-sequence is public data, but the full sequence is secret, except for the sub-sequence part of it). – Vincent Granville Apr 12 at 14:03
• The problem has legal implications. If the highly improbable event occurs, than basically my system is potentially compromised, and it could cost me money (a lot). So I want the probability in question to be $10^{-200}$ or less. – Vincent Granville Apr 12 at 14:17

## 2 Answers

As far as I know, you can compute the complement probability (i.e. the probability of the sub-sequence not appearing in the sequence) using the Goulden-Jackson cluster method. The original paper is this one, but you may be able to find more practical explanations online.

If you just need an upperbound, that is much easier.

Let $$X =$$ the number of times the sequence appears. There are $$M-K+1$$ possible starting possitions, so by linearity of expectation, $$E[X] = (M - K + 1) n^{-K} < M n^{-K}.$$

Now $$E[X] = \sum_{k \ge 0} k P(X = k) = \sum_{k \ge 1} k P(X = k) \ge \sum_{k \ge 1} P(X=k) = P(X \ge 1) =$$ prob that the $$K$$-sequence appears at least once. So this prob is upperbounded by $$E[X] < M n^{-K}$$.

I am saying exactly the same thing as all the various comments, except that the above also formally proves it is an upperbound.