Re: coupon collector problem

In article <1133304625.063837.313260@z14g2000cwz.googlegroups.com>,
yezi <ye_line@hotmail.com> wrote:
>Hi: all:

>I am reading the paper" Practical Network Support for IP Traceback" ,
>in this paper , there is one sentence related to the " coupon collector
>problem", however I am new with that topic. Just paste the sentence
>here, what I want to ask, what is expension of d(ln(d)+o(1)) , how can
>draw the conclusion.

>Thanks
"
>Finally,as per the well-known coupon collector problem, the number
>of trials required to select one of each of d equi-probable items
>is d(ln(d) + O(1))."

The length of time to get the k-th item is geometric with
mean d/(d-k+1), and these are independent. So the mean of
the total is d*\sum_1^d 1/k, and the sum is
ln(d) + \gamma + 1/(2d) + smaller terms, and the variance
is approximately d^2*\sum 1/k^2, or approximately d^2*pi^2/6.
The random term is NOT approximately normal, and it is likely
to be the fact that the random term is larger than the fixed
correction.

-- 
This address is for information only.  I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Department of Statistics, Purdue University
hrubin@stat.purdue.edu         Phone: (765)494-6054   FAX: (765)494-0558