# Probability of picking all elements in a set

I was studying the birthday paradox and got curious about a related, but slightly different problem. Lets say I have a set S, that has n unique elements. If I randomly pick k elements from the set (assuming equal probability of picking any element), the probability that I'll have picked all the elements in the set, when k=n is n!/n^n.

Now, what would be the value of k for probability of picking all elements in the set to be > 0.9 (or some constant).

A simpler variation would be - how many times should I flip a coin to have a probability > 0.9 to have thrown heads and tails at least once.

-
 Come on, I am sure you can figure out the so-called simpler variation. – Did Jun 6 '11 at 20:51

Your first question is about a famous problem called the Coupon Collector's Problem.

Look in the Wikipedia write-up, under tail estimates. That will give you enough information to estimate, with reasonable accuracy, the $k$ that gives you a $90$ percent chance of having seen a complete collection of coupons.

-
 Thanks! That helped. I also went through math.uni-konstanz.de/~kohlmann/ftp/applets/… to understand this more. – Shriram Jun 7 '11 at 1:11

Hint: If you throw a coin $k$ times and it's not true that both heads and tails have come up, what must your throws be?

If you're not sure, try some small value of $k$, say $k = 3$. List all possible throws, and cross out those that have both heads and tails. What remains?

-

The general probability of having picked all the elements after a sample size $k$ with replacement is

$$\frac{S_2 (k,n) \; n!}{ n^k}$$

where $S_2 (k,n)$ is a Stirling number of the second kind. You want this to be more than 0.9.

For $n=2$, you have $S_2 (k,2) = 2^{k-1}-1$ for $k \gt 2$ so you want

$$\frac{(2^{k-1}-1) \times 2}{ 2^k} \gt 0.9$$

which is true when $2^{k-1} \gt 10$, so with integers you get $k \ge 5$.

-