Some upper and lower bounds on the coupon collector problem

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS

卷:200

Article

Shioda, S.

关键词: coupon collector problem;    bounds;    distribution function;    denial of service attack;    IP traceback;   

DOI  :  10.1016/j.cam.2005.12.011

来源: Elsevier

【 摘 要 】

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. (c) 2006 Elsevier B.V. All rights reserved.

【 授权许可】

Free