Let's say I have balls numbered 1 to 100 in an urn. Every time I pick one at a random, record it as seen and put it back in the urn. How many such picking do I have to perform if I expect to see at least 99 of them?
I am looking for a general solution to such problems, not just answer to this specific problem.
(please feel free to reword my questions, as needed)
Thank you.
This is a variant of the coupon collector's problem, which can be solved using the classical occupancy distribution (see e.g., Johnson and Kotz 1977). Suppose you draw $n$ times from your urn of $m=100$ balls. Letting $1 \leqslant K \leqslant \min(n,m)$ be the total number of different balls you have seen in all draws, this random variable follows a classical occupancy distribution with mass function given by:
$$\mathbb{P}(K(n,m) = k) = \frac{(m)_k \cdot S(n,k)}{m^n} \quad \quad \quad \text{for all } 1 \leqslant k \leqslant \min(n,m),$$
where $(m)_k = \prod_{i=0}^{k-1} (m-i)$ are falling factorials and $S(n,k)$ are the Stirling numbers of the second kind. Now, define $T \equiv T(k,m) \equiv \min \{ n \in \mathbb{N} | K(n,m) \geqslant k \}$ as the number of draws required to see $1 \leqslant k \leqslant m$ different balls. This random variable has distribution function:
$$\begin{equation} \begin{aligned} F_T(t) \equiv \mathbb{P}(T \leqslant t) = \mathbb{P}(K(t,m) \geqslant k) &= \frac{1}{m^n} \sum_{i=k}^{\min(t,m)} (m)_i \cdot S(t,i). \\[6pt] \end{aligned} \end{equation}$$
This distribution function fully describes the behaviour of this random variable. From here it is possible to derive the mass function, expected value, or other aspects of its behaviour. For your particular case you have $m=100$ and $k=99$ so the distribution function is:
$$F_T(t) = \frac{100!}{100^n} \Big[ S(t,99) + S(t,100) \cdot \mathbb{I}(t \geqslant 100) \Big] \quad \quad \quad \text{for all } t \geqslant 99.$$
Johnson, N.L. and Kotz, S. (1977) Urn Models and their Applications. John Wiley and Sons: New York.
