Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Come on, I am sure you can figure out the so-called simpler variation. – Did Jun 6 '11 at 20:51
This answer shows that $$\sum_{k=0}^n(-1)^k\binom{n}{k}\left(1-\frac kn\right)^r$$ is the probability that after $r$ trials, all of $n$ items will be picked with replacement. – robjohn Nov 26 '15 at 14:16
up vote 1 down vote accepted

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.

share|cite|improve this answer
Thanks! That helped. I also went through… 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?

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


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.