> [!Question] Problem > We repeatedly sample from a set of $N$ distinct objects until at least one copy of each distinct object is obtained. Denote $T$ as the number of draws until the every $\{1, 2, \dots , N \}$ is seen, what is the expected value of $T$? # Solutions For $n\geq 1,$ let $x_{n}$ denote the number of draws until we collect the $n$th unique coupon after collecting $(n-1)$ unique coupons. Then $x_{n}\sim \text{Geom}(p_{n})$ where $\text{Geom}(p_{n})$ denotes a [[Geometric Distribution|geometric distribution]] with parameter $p_{n}$ and $p_{n}=\frac{N-n+1}{N}.$ By linearity of expectation $\begin{align} \mathbb{E}[T]&=\mathbb{E}\left( \sum_{n=1}^{N } x_{n}\right)=\sum_{n=1}^{N}\mathbb{E}[x_{n}]=\frac{N}{N}+\frac{N}{N-1}+\dots+\frac{N}{1} \\ &= N\left( 1+\frac{1}{2} + \frac{1}{3} +\dots+\frac{1}{N} \right)=NH_{N}\approx N(\log N +\gamma) \end{align}$where $H_{N}$ denotes a [[Harmonic Numbers|harmonic number]].