Friday 19 February 2016

probability - Coupon Collecting Problem using Inclusion-Exclusion




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

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...