# expected number of repeats in random strings from different sized alphabets

The question is just for fun, and I feel like I'm missing a clever way of thinking about it.

suppose that you are on an alien planet, and you are trying to learn their language. You break into one of the aliens houses and get on his computer and print the contents of a file by accident. you have to figure out if this document is written in their language, or if it's just a binary file.

the idea here I think is that the alphabet for the language is smaller than the alphabet for a printed binary file. You would expect many more repeats from the string with the smaller language. after some string length, you would be able to give a pretty good estimate of the number of letters in the alphabet from which the text was written.

anyway, the question is, what is the probability of a string of length $n$ chosen randomly with an alphabet of size $m$ will have $k$ unique letters?

-

The number of words of length $n$ that use exactly $k$ letters from an alphabet of size $m$ is

$${m \choose k} k! \, S_{n,k} = \frac{m!}{(m-k)!}S_{n,k}$$

where $S_{n,k}$ is the Stirling number of the second kind, (you can think the alphabet as a set of $m$ urns, and $n$ numbered balls, each one corresponding to a position in the word). The total number of words is $m^n$. Hence the probabilities are given by

$$p_k^{n,m} = \frac{m!}{(m-k)!} \frac{S_{n,k}}{m^n}$$

-
yeah, this is good. $S_{n,k}$ is unlabelled partitions, the $m\choose k$ gives all the label sets and the $k!$ gives all the labelings for each of those sets. This is a good formula to know. –  Zackkenyon Jun 2 '13 at 4:13

The expected number of distinct letters is easy to compute. The distribution of the number of distinct letters is much less pleasant, and I do not know of anything that avoids messy Inclusion/Exclusion.

Let the letters be $a_1,a_2,\dots,a_m$. For any $i$, let $X_i=1$ if the letter $a_i$ occurs in our text, and let $X_i=0$ otherwise. Then the number of different letters is $X_1+X_2+\cdots +X_m$. By the linearility of expectation, we have $$E(X_1+X_2+\cdots+X_m)=E(X_1)+E(X_2)+\cdots +E(X_m).$$ To find the expectation of $X_i$, we find the probability that $X_i=1$. This is $1-\left(\frac{m-1}{m}\right)^n$. So the expected number of distinct letters is $$m\left( 1-\left(\frac{m-1}{m}\right)^n \right).$$

-
Yeah it's the distribution that was giving me trouble. Although this is a nice way of thinking about the expectation. –  Zackkenyon Jun 2 '13 at 3:32