# What is the average number of random selections it would take to have picked every element of a set and the size of that set, n?

I've been discussing this question with my AP statistics teacher and we're both racking our brains as to how this probability distribution would look. The problem came up when looking at the scenario of determining how many simple random samples you would expect to run over a population before having sampled the entire population.

If you take a set of size n and begin randomly selecting elements one at a time with replacement, your initial probability of selecting a unique element given one random selection is 1. Hence p(1 in 1) = $1$.

For your second selection, the probability of not selecting a new element (i.e. getting only one unique element out of two selections) is equal to p(1 in 2) = $\frac{1}{n}$. Similarly, p(2 in 2) = $\frac{n-1}{n}$

This is where it gets slightly complicated; the chain of selections after p(2 in 2) now has a probability of $\frac{2}{n}$ that an element is selected again and only $\frac{n-2}{n}$ that a new element is selected. However, these probabilities remain the same for the selections after p(1 in 2) since only one unique element has been selected in that scenario. This means probability is dependent on order of unique/non-unique selections, and for probabilities like p(2 in 3) where multiple orders exist, the probability in general is the sum of the probabilities of the individual orders.

Just to solidify this through an example:

p(1 in 3) = $\frac{1}{n^2}$,

p(2 in 3) = $\frac{1}{n}*\frac{n-1}{n} + \frac{n-1}{n} * \frac{2}{n}$ = $\frac{3(n-1)}{n^2}$

p(3 in 3) = $\frac{(n-1)(n-2)}{n^2}$

If I can clarify anything please let me know; I'd be very interested to know what statistical analysis you'd have to do for this problem!

• Look at Wikipedia, Coupn Collector's Problem. The distribution is unpleasant to get at, but the mean is quite accessible. – André Nicolas Apr 19 '16 at 19:03
• The book Randomized Algorithms by Motwani and Raghavan is also a cornucopia for this sort of questions: see Chapter 3.6 (specifically on the Coupon Collector). – Clement C. Apr 19 '16 at 19:05

The probability after $r$ draws from $n$ items with replacement that you have collected $M=m$ unique items is
$$\Pr(M=m) =\dfrac{S_2(r,m) \, n!}{n^r \, (n-m)!}$$
where $S_2(r,m)$ are Stirling numbers of the second kind
while the the expected number of unique items is more easily calculated by considering the probability an item is not collected $$E[M]=n - n\left(1-\frac{1}{n}\right)^r$$
with variance $$\mathop{Var}(M)=n\left(1-\frac{1}{n}\right)^r + n^2\left(1-\frac{1}{n}\right)\left(1-\frac{2}{n}\right)^r -n^2\left(1-\frac{1}{n}\right)^{2r}$$