Geometric distribution

A geometric distribution models the number of independent Bernoulli trials needed to obtain the first success. On the convention supported by $1,2,\dots$, its mass is $(1-p{)}^{k-1}p$ and its mean is $1/p$. On the failures-before-first-success convention supported by $0,1,\dots$, its mass is $(1-p{)}^{k}p$ and its mean is $(1-p)/p$. Both conventions have variance $(1-p)/p^2$.

For a positive-integer geometric distribution $P(N=j)=p{q}^{j-1}$ with $q=1-p$, the capped time has masses $p{q}^{j-1}$ for $1\le j<k$ and $q^{k-1}$ at $k$. The last mass includes all later arrivals, not only $N=k$. Its probability generating function and expected value areThe expectation follows either by differentiating the PGF or summing the tail probabilities up to $k$.

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 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.