OurBigBook.comSite Source code

Coupon collector problem

When independent uniform draws are made from

n

types, the time

T_{n}

until every type has appeared decomposes as a sum of independent geometric waiting times with parameters

1, \frac{n - 1}{n}, \dots, \frac{1}{n} .

Consequently

E T_{n} = n H_{n}, var (T_{n}) \leq n^{2} \sum_{j = 1}^{\infty} \frac{1}{j ^{2}},

and Chebyshev's inequality gives

T_{n} / (n lo g n) \to 1

in probability.

 Ancestors (8)

 Incoming links (1)

Solution