Some upper and lower bounds on the coupon collector problem (Q859873)

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.