Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
This might help math.stackexchange.com/questions/5775/… –  Byron Schmuland Oct 13 '11 at 12:05
    
    
@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

2 Answers 2

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

share|improve this answer
    
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
1  
I like the use of recursion. It makes for a nice derivation. (+1) –  robjohn Oct 13 '11 at 17:31
1  
@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} $$

share|improve this answer
3  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.