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.

  • 3
    $\begingroup$ This generalizes the coupon collector problem. I suspect some of the posts on it may have already developed formulas for the full distribution, so check them out. $\endgroup$
    – whuber
    Jan 24 '17 at 17:00
  • 1
    $\begingroup$ Thank you. That helped a lot. I actually just hoped on to Wikipedia (en.wikipedia.org/wiki/Coupon_collector's_problem) once I knew what is is called :). $\endgroup$
    – Vijay
    Jan 24 '17 at 17:08
  • $\begingroup$ I just found my old solution at stats.stackexchange.com/a/88156/919. A tiny modification will give you an expression (albeit a little unwieldy) for the full distribution. $\endgroup$
    – whuber
    Jan 24 '17 at 17:10

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.