# Finding expected number of distinct values selected from a set of integers

I have a set of $n$ integers $\{1, . . . , n\}$, and I select three values with replacement. How can I find the expected number of distinct values?

Note each value is chosen uniformly and independently.

-
This might help math.stackexchange.com/questions/5775/… – Byron Schmuland Oct 13 '11 at 12:05
– Mike Spivey Oct 13 '11 at 21:42
@Mike Thanks for the additional reference. Looks like this problem is an evergreen, or a chestnut! – Byron Schmuland Oct 13 '11 at 21:49
@Byron: I give links to some other examples of using indicator variables in my answer to that question. And the more complicated problem of the expected number of distinct items when drawing $k$ pairs at random was asked a while back. Both the "with replacement" and "without replacement" answers are given. – Mike Spivey Oct 13 '11 at 22:34

The probability that the first item was not chosen before is $1$. The probability that the second item was not chosen before is $\frac{n-1}n$. The probability that the third item was not chosen before is $\frac{n-2}n$ if the two first items are different and $\frac{n-1}n$ if the two first items coincide. The two first items are different with probability $\frac{n-1}n$ and they coincide with probability $\frac{1}n$. Hence the expected number of distinct items is $$1+\frac{n-1}n+\frac{n-2}n\times\frac{n-1}n+\frac{n-1}n\times\frac1n=\frac{3n^2-3n+1}{n^2}.$$

More generally, consider the number $N_k$ of different items chosen after $k$ picks. Then $N_0=0$ almost surely and, knowing $N_k$ the probability to pick a new item at time $k+1$ is $(n-N_k)/n$ hence $\mathrm E(N_{k+1}\mid N_k)=N_k+(n-N_k)/n$ almost surely.

This shows that the expected number of different items after $k$ picks $n_k=\mathrm E(N_k)$ is such that $n_0=0$ and $n_{k+1}=n_k+(n-n_k)/n=1+a_nn_k$ for every $k\geqslant0$, with $a_n=(n-1)/n$. Thus, for every $k\geqslant0$, $n_k=(1-a_n^k)/(1-a_n)$ or, equivalently, $$n_k=n\,\frac{n^k-(n-1)^k}{n^{k}}=\sum\limits_{i=0}^{k-1}(-1)^{i}{k\choose i+1}\frac1{n^i}.$$

-
This was very helpful. I just have one question, "if the two first items are different, which happens with probability n−1/n, and n−1/n.." is their a typo there should it be n-1/n and n-2/n? – Alex Oct 13 '11 at 8:08
There was no typo. I rephrased. – Did Oct 13 '11 at 8:56
I like the use of recursion. It makes for a nice derivation. (+1) – robjohn Oct 13 '11 at 17:31
@robjohn, yep, a nice recursion based on conditional expectations is simply the thing to make a probabilist happy for hours... – Did Oct 13 '11 at 22:20

Didier's method uses recursion very nicely to arrive at the expected number. I arrived at the same answer using more mundane computations.

Let's generalize by picking $p$ numbers from $1\dots n$ with replacement. Let us compute the probability of choosing $d$ distinct numbers. Choose one of the $\binom{n}{d}$ sets of $d$ distinct numbers. The probability of selecting all $p$ picks from those $d$ distinct numbers is $\left(\frac{d}{n}\right)^p$. However, this also counts cases where some of the $d$ numbers were not chosen. Inclusion-exclusion says that the probability of picking all of those $d$ is $$\sum_k(-1)^{k}\binom{d}{d-k}\left(\frac{d-k}{n}\right)^p=\sum_k(-1)^{d-k}\binom{d}{k}\left(\frac{k}{n}\right)^p\tag{1}$$ Thus, the probability of picking exactly $d$ distinct items is $\binom{n}{d}$ times $(1)$. The expected value is therefore \begin{align} &\sum_d\sum_k(-1)^{d-k}d\binom{n}{d}\binom{d}{k}\left(\frac{k}{n}\right)^p\\ &=\sum_d\sum_k(-1)^{d-k}d\binom{n}{k}\binom{n-k}{n-d}\left(\frac{k}{n}\right)^p\\ &=n-\sum_d\sum_k(-1)^{d-k}(n-d)\binom{n}{k}\binom{n-k}{n-d}\left(\frac{k}{n}\right)^p\\ &=n-\sum_d\sum_k(-1)^{d-k}(n-k)\binom{n}{k}\binom{n-k-1}{n-d-1}\left(\frac{k}{n}\right)^p\\ &=n-\sum_k(n-k)\binom{n}{k}\delta(k-n-1)\left(\frac{k}{n}\right)^p\\ &=n-n\left(\frac{n-1}{n}\right)^p\\ &=n\left(1-\left(\frac{n-1}{n}\right)^p\right)\tag{2} \end{align}

-
I think that Dinesh's solution with indicator random variables is also quite elegant: math.stackexchange.com/questions/5775/… – Byron Schmuland Oct 13 '11 at 17:33
@Byron: yes, indeed! The probability that all $p$ picks are not $1$ is $\left(\frac{n-1}{n}\right)^p$ so the expected value of $1$ is $1-\left(\frac{n-1}{n}\right)^p$ and so the total expected value is $n\left(1-\left(\frac{n-1}{n}\right)^p\right)$. Very neat! – robjohn Oct 13 '11 at 20:06