Distinct coupon types after a thousand purchases

Question

Each purchase gives one coupon, a uniformly random type out of 200, independently. You make 1000 purchases. On average, how many distinct coupon types do you end up with?

Accepted Answer

Work one type at a time and add up with linearity of expectation. A given type is missing only if all 1000 purchases avoid it: P(	ext{type missing}) = \left(\frac{199}{200}ight)^{1000} \approx 0.0066. So the chance you have that type is 1 - 0.0066 = 0.9934. With 200 types, the expected number collected is E[	ext{distinct types}] = 200 	imes \left(1 - \left(	frac{199}{200}ight)^{1000}ight) \approx 200 	imes 0.9934 \approx 198.7. So you likely have almost all 200 types, missing just one or two on average. (Filling in those last few is the slow part of the coupon-collector problem.) T…

Distinct coupon types after a thousand purchases

Your answer

Discussion

Learn the concepts

Related questions