Some upper and lower bounds on the coupon collector problem
type: Item
instance of: scholarly article
title: Some upper and lower bounds on the coupon collector problem
zbMATH Open document ID: 1113.60022
published in: Journal of Computational and Applied Mathematics
publication date: 2007-01-22T00:00:00Z
review text: Let there be \(N\) types of objects in a box. They are repeatedly sampled and the probability to sample an object of \(i\)th type is \(p_i\). Denote by \(X\) the number of samplings required for detecting (observing) a set of object types indexed by \(i=1,\dots,n\). The author obtains lower and upper bounds for the probability \(P(X>k)\), e.g. \[ P(X>k)\geq\sum_{j=1}^n(1-p_j)^k-\sum_{i=1}^n\sum_{j=i+1}^n(1-p_i-p_j) ^k=L(k), \] \[ P(X>k)\leq\sum_{j=1}^n(1-p_j)^k=U(k). \] It is shown that \((U(k)-L(k))/P(X>k)\sim \alpha^k\) as \(k\to\infty\) for some \(0<\alpha<1\). These results are applied for the estimation of detecting cost in probabilistic packet marking schemes for IP traceback problem in the Internet. Numerical examples are presented.
Mathematics Subject Classification ID: 60E15
Mathematics Subject Classification ID: 90B18
Mathematics Subject Classification ID: 60C05
zbMATH DE Number: 5117674
zbMATH Keywords: denial of service attack
zbMATH Keywords: IP traceback
zbMATH Keywords: probabilistic-packet-marking
zbMATH Keywords: Schur-convex function
author: Shigeo Shioda
reviewed by: R. E. Maiboroda
MaRDI profile type: Publication
full work available at URL: j.cam.2005.12.011
OpenAlex ID: W2097462212
cites work: General asymptotic estimates for the coupon collector problem
cites work: Q5512461
cites work: Birthday paradox, coupon collectors, caching algorithms and self- organizing search
cites work: Extreme value distributions for random coupon collector and birthday problems
cites work: Inequalities: theory of majorization and its applications
cites work: Some bounds on the coupon collector problem
cites work: Asymptotics for the random coupon collector problem
DOI: 10.1016/J.CAM.2005.12.011
description: scientific article; zbMATH DE number 5117674