Suppose we have n boxes and we start randomly and independently throwing balls into the boxes.

(a) For a given box, what is the expected number of balls we need to throw before one of the balls lands in that box?

(b) What is the expected number of balls we need to throw before every bin contains at least one ball?


closed as off-topic by TMM, Michael Hoppe, Magdiragdag, user99914, Andrew D. Hwang Mar 11 '14 at 19:25

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – TMM, Michael Hoppe, Magdiragdag, Community, Andrew D. Hwang
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ $\ln(n)$ and $n\ln(n)$ Check this book $\endgroup$ – Guy Mar 11 '14 at 11:22
  • $\begingroup$ @Sabyasachi: The answer to the first is definitely $n$, not $\ln n$. The second is indeed $n \ln n$, by the coupon-collector problem. $\endgroup$ – ShreevatsaR Mar 11 '14 at 15:52
  • $\begingroup$ @ShreevatsaR $n$ is you consider worst case. $\ln(n)$ in average case. $\endgroup$ – Guy Mar 11 '14 at 15:53
  • $\begingroup$ Although I guess we're supposed to consider worst case anyway. $\endgroup$ – Guy Mar 11 '14 at 15:54
  • $\begingroup$ @Sabyasachi: No, the question is precise (there is no such thing as average case or worst case): it wants the expected number of balls thrown until one lands in that box, which is $n$. See answer by Stefanos below. $\endgroup$ – ShreevatsaR Mar 11 '14 at 15:54

For (a). This is the geometric distribution with parameter $1/n$ since we count trials until the first success (with success we denote the event that a ball lands in the given box) and the probability of success in each trial is equal to $1/n$, assuming that each ball has equal probability to land in each box. So the expected number of trials is the expectation of the Geometric random variable $X$ with parameter $p=1/n$ which is equal to $$E[X]=\frac{1}{p}=\frac{1}{\frac{1}{n}}=n$$ (Note however that this is the expected number of trials until one ball lands in the given box. If you mean "before one lands" then you should take the geometric starting from $0$ which has expectation $(1-p)/p$ which is equal to $n-1$ for $p=1/n$. Same way of thinking, slight difference, it is only that I do not understand properly which of the two is required.)


For b) read about the coupon collector's problem. http://en.wikipedia.org/wiki/Coupon_collector's_problem


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