Number of different combinations in a sample I hail from Mathematica SE. A friend of mine asked me a statistics question (I'm an economist and am assumed to know such things) which kind of stumped me, since I usually deal with non-discrete statistics.
Say you have a DNA strand with 20 positions, each of which can have one of four nucleotides (A,C,G,T). There is a "correct" combination, say A,T,G,C,C,....
For each position the probability of having the correct nucleotid is 85%. The probability of having one of the others is 5% each.
Now assume you have a sample of 100M strands. My question is : What is the most likely number of different combinations (20 nucleotides in a specific order) in our sample?
Bonus question: Could you point me to some further reading on the subject, as I am interested in refreshing my memory on discrete statistics.
Thanks in advance.
 A: tl;dr: the expected number of distinct sequences is around ten million, getting the most likely number of distinct sequences is not easy, and Knuth's Concrete Mathematics is a good book on the topic.
I can give you the expected number of different combinations, this is one is easy because expectation is linear. Let $a_i$ be the random variable which is $1$ is combination $i$ is in the sample, and $0$ otherwise. $m = \sum_{i=1}^{n} a_i$ is a random variable which represents the number of distinct combinations present in the sample. Clearly $m \leq n=4^{20}$.
Now the part which still amazes me to this day... $E(m) = \sum_{i=1}^n E(a_i) = \sum_{i=1}^n p(a_i=1)$
So what is the probability that a particular combination is sampled? It depends on the number of correct nucleotides. One combinaiton has all the nucleotides correct and is sampled with probability $0.85^{20} = q^k$ (in the future, $q=0.85$ and $k=20$).
There are also $3k$ combinations where one nucleotide is wrong, and each has a probability $\frac{1}{3}(1-q)q^{k-1}$ of being picked.
In general there are $3^r {k \choose r}$ combinations where $r$ nucleotides are wrong, each with a probability $\left(\frac{1}{3}\right)^r(1-q)^r q^{k-r}$ of being picked.
As a sanity check
$$\sum_{r=0}^k 3^r {k \choose r} \left(\frac{1}{3}\right)^r(1-q)^r q^{k-r} = 1$$
For each possible combination, we get $N=10^8$ tries. This gives us the expectation
$$E(m) = \sum_{r=0}^k 3^r {k \choose r} \left(1-\left(1-\left(\frac{1}{3}\right)^r(1-q)^r q^{k-r} \right)^N\right)$$
numerically, this is about $1.03 \times 10^7$ about one hundred thousandth of the total number of combinations.

The most likely number of distinct combinations is harder to obtain. One route would be to compute the probability of obtaining exactly $d$ distinct elements with $d = d_0 + d_1 + \ldots + d_r$  distinct elements having respectively $d_i$ distinct elements with $i$ incorrect nucleotides. 
When the probabilities are uniform, the probability is given by 
$$\frac{1}{n^N} d!{n \choose d}\genfrac\{\}{0pt}{}{N}{d}$$
where $\genfrac\{\}{0pt}{}{N}{d}$ is a Stirling number of the second kind and represents the number of way to partition the $N$ draws in $d$ non empty subsets. Intuitively, that formula simply counts the number of draws with $d$ distinct elements by saying: pick $d$ distinct elements, order them and assign them to different partitions of the sample.
Let's put it all together, we get
$$p(d) = \sum_{\substack{d_0+\ldots+d_k=d \\ N_0+\ldots+N_k=N}} \left(  N! \prod_{r=0}^{k}  \genfrac\{\}{0pt}{}{N_r}{d_r} {3^r{k \choose r} \choose d_r} \frac{d_r!}{N_r!}\left(\left(\frac{1-q}{3}\right)^r q^{k-r}\right)^{N_r} \right)$$
Note that there are on the order of $(dn)^k$ terms in that sum. You could conceivably approximate it using Monte-Carlo integration with importance sampling, evaluate this for multiple values of $d$ and find the location of the maximum this way. A good approach would be to sample $d_1, \ldots, d_k$ and $N_1, \ldots, N_k$ using two multinomial distributions and adapt the parameters of these distributions using the cross-entropy method.

Discrete statistics involve a lot of combinatorial enumeration. A very enjoyable book on the topic is Knuth's Concrete Mathematics
