×

Optimality results for coupon collection. (English) Zbl 1353.60089

Summary: We consider the coupon collection problem, where each coupon is one of the types \(1,\ldots,s\) with probabilities given by a vector \(\mathbf{p}\). For specified numbers \(r_{1},\ldots,r_{s}\), we are interested in finding \(\mathbf{p}\) that minimizes the expected time to obtain at least \(r_{i}\) type-\(i\) coupons for all \(i=1,\ldots,s\). For example, for \(s=2\), \(r_{1}=1\), and \(r_{2}=r\), we show that \(p_{1}=(\log r-\log(\log r))/r\) is close to optimal.

MSC:

60K99 Special processes
60C05 Combinatorial probability
49J55 Existence of optimal solutions to problems involving randomness
Full Text: DOI