If we throw $m$ balls into $n$ bins independently and uniformly at random, what is the expected number of balls that are in a bin containing at least one other ball?

My reasoning for this was that for a particular ball, the probability that some other ball falls in the same bin is $1 - P[$No other ball falls in the same bin$] = 1 - (1 - \frac1n)^{m-1}$. Thus the expected number of balls in a bin with at least 1 other ball (by independence and linearity of expectation) is $m(1 - (1 - \frac1n)^{m-1})$.

However, I am simulating this in Python and am getting a large average error between the simulated and expected value over 1000 trials (with $m = 20$, $n = 35$). Is the above recurrence incorrect, or is my simulation probably incorrect? Might it have anything to do with the fact that the expected value is real-valued while the simulation produces integer values?

  • $\begingroup$ The expression for the expectation is correct. The fact that any particular result of throwing $20$ balls results in an integer should not be relevant, the average of $1000$ counts will almost certainly not be an integer. $\endgroup$ – André Nicolas Dec 6 '15 at 7:04
  • $\begingroup$ Turns out, I had a bug in my program. I was raising the outer parenthetical expression to the $m-1$ instead of the inner one. Darn parentheses :) $\endgroup$ – Trent Bing Dec 6 '15 at 7:22
  • $\begingroup$ The expectation calculation was totally clear. Of course, changing wording slightly changes the answer a lot, as in mean number of bins with more than one occupant. $\endgroup$ – André Nicolas Dec 6 '15 at 7:31

Your Answer

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

Browse other questions tagged or ask your own question.