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.
Answer
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.
No comments:
Post a Comment