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.
 A: 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}$$
A: 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.
A: 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$.
