Yet another balls and boxes problem; minimum number of throws so that we have no empty boxes.

Question

I managed to figure out how many empty boxes will be left given n amount of throws, just having a hard time figuring out the minimum number of throws necessary so that we have no empty boxes. Would it have to do with the binomial distribution?

Answer 1

The problem is a classical one, usually called the Coupon Collector's Problem. There is a substantial literature. The Wikipedia article linked to gives a reasonably good summary.

If $T$ is the "time" (number of balls) until no box is empty, then the expectation of $T$ is fairly straightforward to get at. It turns out that $$E(T)=nH_n,$$ where $H_n$ is the $n$-th harmonic number, that is, $H(n)=1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}$. The number $H_n$ grows like $\ln n$. For finer estimates, google harmonic number.

The distribution of $T$ is very complicated. But there are reasonably good tail estimates that let us estimate $\Pr(T\gt t)$ with reasonable accuracy.

Answer 2

If $T$ is the "time" (number of balls) until no box is empty, then the distribution of $T$ is easy to describe if you are willing to use Stirling numbers of the second kind. We have for $t\geq n$, $$\mathbb{P}(T\leq t)=n^{-t}\, n!\,{t\brace n}\quad\mbox{and}\quad \mathbb{P}(T = t)=n^{-t}\, n!\,{t-1\brace n-1}.$$