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

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?

-
Can't have certainty no matter what the number of throws is. So need to specify a proability, like minimum number of throws so that with probability $\gt 0.99$ there are no empty boxes. – André Nicolas Jun 17 '13 at 23:33
@AndréNicolas Or simply the expected number of tosses, rather than a probability threshhold. – Thomas Andrews Jun 17 '13 at 23:35

## 2 Answers

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.

-

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}.$$

-