5
$\begingroup$

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.

  • 0
    [This answer](http://math.stackexchange.com/a/266578) 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.2015-11-26

3 Answers 3

2

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.

  • 0
    Thanks! That helped. I also went through http://www.math.uni-konstanz.de/~kohlmann/ftp/applets/CouponCollectorExperiment.html to understand this more.2011-06-07
1

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

0

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?