A Generalized Coupon Collector Problem

Abstract

This paper provides analysis to a generalized version of the coupon collector problem, in which the collector gets $d$ distinct coupons each run and she chooses the one that she has the least so far. On the asymptotic case when the number of coupons $n$ goes to infinity, we show that on average $\frac{n\log n}{d}+\frac{n}{d}(m-1)\log \log n+O(mn)$ runs are needed to collect $m$ sets of coupons. An efficient exact algorithm is also developed for any finite case to compute the average needed runs exactly. Numerical examples are provided to verify our theoretical predictions.

20 pages, 6 figures, preprint

Cited by in corpus (2)

• Practical Bounds on Optimal Caching with Variable Object Sizes
• Nurgle: Exacerbating Resource Consumption in Blockchain State Storage via MPT Manipulation