Expected time of drawing all types of coins from a large pile

70 Views Asked by At

I've been working on the following question but am uncertain of how to solve it

Consider an infinitely large pile of coins. Each coin has a number {1, 2, . . . , n} written on it, and these numbers appear in equal propor- tions in the pile. Suppose that you keep drawing coins from this pile until the first time, T , that you have at least one coin of each number {1, 2, . . . , n}. Find the expected value of T.

1

There are 1 best solutions below

1
On

Let $X_i(k):=\mathbb{P}\{ i^{th} \mbox{ type of coin is drawn for the first time on the }k^{th} \mbox{draw} \}$. This random variable follows a geometric distribution with parameter $p=\frac{1}{n}$.
Let $T:=\sum_{i=1}^n X_i$ then: \begin{equation} \mathbb{E}[T]=\sum_{i=1}^n\mathbb{E}[X_i]=\sum_{i=1}^n n = n^2. \end{equation}