# Combinatorics problem in an "autocomplete" application

An alphabet is given, consisting of $$26$$ letters:

$$a, b, c,..., z$$

$$N$$ random strings of length $$L$$ are created using this alphabet. One can assume uniform distribution wrt choice of letters, and repetitions are allowed (both repetitions of a particular letter within a string, and repetitions of whole strings).

Now, in the same fashion, a single random string (let's call it $$S$$) is created of length $$l$$ ($$l < L$$).

What is the probability that exactly $$k$$ strings from previously chosen set of random strings begin with the $$S$$?

I know I can easily do a computer simulation, but is there a closed formula that depends only on $$N$$, $$L$$, $$l$$ and $$k$$?

This problem comes up in some auto-complete string manipulation application.

• Do you mean at least $k$ strings or exactly $k$ strings? Oct 5, 2020 at 16:46
• @saulspatz Exactly $k$ strings. I am going to edit the question for this unclarity. Oct 5, 2020 at 16:47

Let $$p$$ be the probability that a string starts with $$S$$. The probability that exactly $$k$$ of $$N$$ strings start with $$S$$ is $$\binom Nkp^k(1-p)^{N-k}$$ because there are $$\binom Nk$$ ways to choose which strings start with $$S$$.

Now $$p=26^{-l}$$ since for each of the first $$l$$ letters of the string, the probability that it equals the appropriate letter from $$S$$ is $$\frac1{26}$$. So the final answer is $$\binom Nk26^{-lk}\left(1-26^{-l}\right)^{N-k}$$

The other answers have already given the exact answer, which is binomially distributed. However, since the number of strings is probably very large, and the probability of a match with each string is certainly very small, the Poisson approximation can also be very useful here.

Out of the $$N$$ strings, the expected number of matches is $$\frac{N}{26^l}$$. If we approximate by a Poisson random variable with mean $$\frac{N}{26^l}$$, the probability of getting exactly $$k$$ matches is $$e^{-N/26^l} \cdot \frac{(N/26^l)^k}{k!}.$$ This will be extremely close to the binomial probability, but it's easier to compute.

The probability that any given randomly generated string begins with the string $$S$$ is equal to

$$p = \Big(\frac{1}{26}\Big)^l$$

because each of the $$l$$ characters must match, and the probability of a match is $$1/26$$ for each character.

So the probability that exactly $$k$$ of the $$N$$ random strings begin with $$S$$ is equal to

$$\binom{N}{k}p^k (1-p)^{N-k} = \binom{N}{k}\Big(\frac{1}{26}\Big)^{lk}\Big(1 - \Big(\frac{1}{26}\Big)^l\Big)^{N-k}$$

Note that this is completely independent of the value of $$L$$, so long as $$L > l$$. This is because only the first $$l$$ characters of each random string have any bearing on whether or not each string begins with $$S$$.