I am very new to probability and combinatorics.
I am trying to solve Coupon Collection Problem using Inclusion-Exclusion formula.
I found a lot of references her a some:
http://en.wikipedia.org/wiki/Coupon_collector%27s_problem
Using Recursion to Solve Coupon Collector
but they all seem concern with expected time to collect all N coupons form what my problem is asking the following:
Suppose there are N coupons after buying n boxes what is the probability that at least one each type has been collected.
Thanks
Answer
Hint: Consider the inclusion-exclusion principle as stated in Wikipedia: Given events $A_1,\ldots,A_N$, we are interested in the probability that at least one of them occurs. In your case, $A_i$ is the event that coupon $i$ never appears. The probability that you're after is $1-\Pr[A_1 \lor \cdots \lor A_N]$. It remains to find a formula for the probability that a set $S$ of coupons never appears, and to plug these probabilities into the inclusion-exclusion formula.
No comments:
Post a Comment