Monday, 29 April 2013

probability - Coupon Collector's Problem with X amount of coupons already collected.




I am having an issue with understanding how to calculate a specific case of the Coupon Collector's Problem. Say I have a set of 198 coupons. I learned how to find the estimated amount of draws to see all 198 coupons, using the following equation:



nnk=11k



It turns out that for n=198, the expected number of draws is approximately 1162. Let's assume, however, that I already have some of the coupons, say 50. How should I go about solving the same problem, given that I've already collected X of them?


Answer



Based on the corresponding thread on Wikipedia. The expected time to draw all n coupons equals:




E[T]=E[t1]+E[t2]++E[tn]



with ti the time needed to collect the ith coupon once i1 coupons have been drawn. Once i1 tickets have been drawn, there are ni+1 unseen coupons left. The probability pi of selecting a new coupon thus equals ni+1n, and the expected number of draws needed to draw a new coupon equals 1pi=nni+1. As such, the expected value for the time needed to draw all n coupons can be calculated as:



E[T]=nn+nn1++n1=nnk=11k



In this case, however, we have already drawn X unique coupons. As such, the estimated number of draws needed to find all n coupons equals:



E[T]=E[tX+1]+E[tX+2]++E[tn]=nnXk=11k


No comments:

Post a Comment

real analysis - How to find limhrightarrow0fracsin(ha)h

How to find lim without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...