Some upper and lower bounds on the coupon collector problem
作者:
Highlights:
•
摘要
The classical coupon collector problem is closely related to probabilistic-packet-marking (PPM) schemes for IP traceback problem in the Internet. In this paper, we study the classical coupon collector problem, and derive some upper and lower bounds of the complementary cumulative distribution function (ccdf) of the number of objects (coupons) that one has to check in order to detect a set of different objects. The derived bounds require much less computation than the exact formula. We numerically find that the proposed bounds are very close to the actual ccdf when detecting probabilities are set to the values common to the PPM schemes.
论文关键词:60C05,Coupon collector problem,Bounds,Distribution function,Denial of service attack,IP traceback
论文评审过程:Received 26 September 2005, Revised 12 December 2005, Available online 3 February 2006.
论文官网地址:https://doi.org/10.1016/j.cam.2005.12.011