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:
nn∑k=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 i−1 coupons have been drawn. Once i−1 tickets have been drawn, there are n−i+1 unseen coupons left. The probability pi of selecting a new coupon thus equals n−i+1n, and the expected number of draws needed to draw a new coupon equals 1pi=nn−i+1. As such, the expected value for the time needed to draw all n coupons can be calculated as:
E[T]=nn+nn−1+…+n1=nn∑k=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]=nn−X∑k=11k
No comments:
Post a Comment