Consecutive coupon collection

312 Views Asked by At

This question has remained unanswered. In its edited form, it asks for a lower bound on the expected number of draws required to collect all coupons in a modified coupon collector's problem in which draws can yield more than one coupon and the coupon types within one draw are consecutive.

I was hoping to show that for small consecutive draws (low $q$ in the linked question) the expected number of coupons drawn is bounded below by the expected number of coupons drawn in the standard coupon collector's problem, but to my surprise simulations showed that this is actually an upper bound. This is clear enough for large consecutive draws – in the extreme case in which every draw contains all $n$ coupons, we need to draw only $n$ coupons instead of $O(n\log n)$, and if every draw contains $n/2$ consecutive coupons, this is still clearly favourable, but intuitively I would have expected draws of just two consecutive coupons to be unfavourable, since they "explore the sample space" more slowly. The simulations show, however, that even in this case there's a slight improvement.

Can we prove that tending to collect consecutive coupons reduces the expected number of coupons drawn?

I intentionally phrased the question somewhat vaguely so you can use whatever "tendency to collect consecutively" might allow a proof; if you want a concrete model, you can use either the one in the linked question, where the number of consecutive coupons drawn in each draw is geometrically distributed, or you could draw a fixed number $k$ of consecutive coupons in each draw. For both cases, simulations show that the expected number of coupons drawn is reduced compared to the standard coupon collector's problem.