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 parametersConsequentlyand Chebyshev's inequality gives $T_n/(n\log n)\to 1$ in probability.

For independent coupon labels arriving at rate $\lambda$, Poisson thinning makes the type-specific first arrival times independent exponentials of rates $\lambda p_j$. Completion time is their maximum. Its distribution is $\mathbb{P}(T<t)={\prod }_j(1-e^{-\lambda p_{j}t})$. The completion count $L$ depends only on the labels and is independent of the exponential interarrival sequence. Therefore $T={\sum }_{k\ge 1}{E}_k{1}_{\{L\ge k\}}$ and nonnegative integration gives the displayed identity. Completion count and its expectation do not depend on arrival rate.

In independent trials with two outcomes of probabilities $p$ and $q=1-p$, let $N$ include the first trial and the trial that first completes the pair. Conditional on the first outcome, $N-1$ has a geometric distribution of parameter $q$ or $p$, with mixture weights $p,q$. The law of total expectation and law of total variance giveThe final term in the unsimplified variance is the variance of the two conditional means; omitting it is incorrect unless $p=q$. Both outcomes must have positive probability for these finite formulas.

For uniform independent draws of $n$ coupon types, the waiting times with $r$ unseen types remaining are independent positive-support geometric distributions of parameter $r/n$. Summing their means gives $n{\sum }_{r=1}^{n}1/r$, and summing their variances gives the displayed formula. Independence follows from fresh draws after each discovery and the fact that the next stage's conditional distribution depends only on the count of remaining types.