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 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|improve this question
    
Come on, I am sure you can figure out the so-called simpler variation. –  Did Jun 6 '11 at 20:51

3 Answers 3

up vote 0 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|improve this answer
    
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?

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

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.