3

I remember that if there are $n$ boxes, and a ball is being thrown repeatedly into one of the boxes with uniform probability, then the expected number of throws before every box has a ball is approximately $nH_n$, which is approximately $n\log n$. The derivation goes as follows:

When we've filled $r<n$ boxes, the probability that we hit an unfilled box with each throw is $(n-r)/n$. The expected number of throws before we hit an unfilled box is $n/(n-r)$. By linearity of expectation, the expected number of throws before we fill all boxes is $\sum_{r=0}^{n-1}n/(n-r) = nH_n$.

What about the expected number of throws before every box has $k$ balls, where $k\geq 1$ is an integer? Is it going to be $kn\log n$.

joriki
  • 238,052
Mika H.
  • 5,639
  • @Macavity Yes, that reminds me of how the derivation goes. When we've filled $r<n$ boxes, the probability that we hit an unfilled box with each throw is $(n-r)/n$. The expected number of throws before we hit an unfilled box is $n/(n-r)$. By linearity of expectation, the expected number of throws before we fill all boxes is $\sum_{r=0}^{n-1}n/(n-r) = nH_n$. – Mika H. Oct 17 '13 at 19:23
  • Still, my main question is left unanswered :) – Mika H. Oct 17 '13 at 19:25
  • I don't think linearity will apply for $k > 1$ to get $k n \log n$ though, as by the time all boxes have a ball at least, several boxes already would have had multiple balls - so $E(k=2) < 2 E(k=1)$ etc. – Macavity Oct 17 '13 at 19:26
  • @Macavity That's exactly what I thought, and that makes the question even more interesting :) – Mika H. Oct 17 '13 at 19:27
  • 1
    Check http://math.stackexchange.com/questions/151267/coupon-collector-problem-for-collecting-set-k-times for essentially a duplicate of this problem. The answer seems $n \log n + (k-1) n \log \log n + O(n)$ – Macavity Oct 17 '13 at 19:39
  • For what its worth, the exact answer when $n=2$ is $2k(1 + 4^{-k} \binom{2k}{k})$. – I. J. Kennedy Oct 17 '13 at 23:09

0 Answers0