Optimal strategy of coupon subset collection when each package contains half of the coupons

摘要

The coupon subset collection is a generalization of the classical coupon collection, where instead of selecting (with replacement) a single coupon, a subset of at most k coupons (known as a "package") is selected in each round. In this paper, we study how to design the pool of packages and assign probabilities to the packages, so as to minimize the expected number of rounds to collect all n distinct coupons. When k divides n, a seemingly optimal strategy is to choose a pool of non-intersecting packages, and assign equal probability to each package in the pool. We prove the optimality of this strategy when the size of the package is half the number coupons, that is, n = 2k.