We describe a generalisation of the classical coupon collector problem, in which at each time step a collector either receives a new copy of a randomly chosen coupon, or looses all their previously collected copies of that coupon. We consider the amount of time it takes this clumsy coupon collector to obtain the full set of n coupons. We conjecture that the mean and variance of the clumsy coupon collector time are exponential in n, but that a standardised clumsy coupon collector time converges to a Gumbel distribution, as is the case for the classical coupon collector.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

The Clumsy Coupon Collector

  • Saksham Aggarwal,
  • Timothy M. Garoni

摘要

We describe a generalisation of the classical coupon collector problem, in which at each time step a collector either receives a new copy of a randomly chosen coupon, or looses all their previously collected copies of that coupon. We consider the amount of time it takes this clumsy coupon collector to obtain the full set of n coupons. We conjecture that the mean and variance of the clumsy coupon collector time are exponential in n, but that a standardised clumsy coupon collector time converges to a Gumbel distribution, as is the case for the classical coupon collector.