2
$\begingroup$

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.

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

3 Answers 3

2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .