Please help me to find error in the following solution for the problem: "We randomly throw $n$ balls into 1000 boxes and note the number of empty boxes. We repeat this experiment large number of times and observe that the average number of boxes with zero balls in experiment is 20. What is $n$?"

I thought that we could use indicator random variables: $X_1=Bern((1-\frac{1}{1000})^n)$, where this $X_1$ indicates that box #1 remains empty after $n$ balls thrown. Then we could say that we have $X_2$, and so on for the other boxes, and they all are $Bern((1-\frac{1}{1000})^n)$ indicator random variables, but they are not independent.

Now, we say that random variable $Y=X_1+...+X_{1000}$. This $Y$ is actually number of empty boxes that we note for each experiment. Then we have that expected value $E[Y]=20$. And since expectation of sum is sum of expected values (even if random variables are not independent) we have $20=n(1-\frac{1}{1000})^n$. This gives me incorrect answer.

I need to understand what I'm missing here. Thank you very much.

  • $\begingroup$ If you think about it, in your setup it is perfectly possible to get $Y = 0$ if all $X_i$'s evaluate to $0$. However this is absurd (unless you throw zero ball , $n = 0$). $\endgroup$ – Zubzub Sep 20 '17 at 7:45
  • $\begingroup$ Zuzzub, rvs are dependent, so your comment is not valid to me as you assume independence $\endgroup$ – asyrov Sep 21 '17 at 17:40
  • $\begingroup$ Unless you can miss boxes when you throw the balls, the RV are not independent since at each throw there is exactly one box which will get a new ball. Again, with you setup there is a non zero probability that non of the box are filled ($Y=0$) after, say, 100000 ball throw. Which cannot happen if we assume we never miss. Conversly, there is also a non zero probability that every box are filled after, say, $1$ ball throw, which is absurd since there are 1000 boxes. $\endgroup$ – Zubzub Sep 22 '17 at 10:38

You have mixed up your formulation,

imagine $n$ balls thrown randomly and independently into 1000 boxes.

In your last step, the formulation for the expected number of empty boxes should be

E[Y] $= 1000{(1- \frac1{1000})}^n =20$

which yields $n= 3910$


This is actually a version of the coupon collector problem.

Let $X_i$ be the number of ball throw needed from having $i$ filled boxes to $i+1$ filled boxes. Clearly $X_0 = 1$. More generally $$X_i \sim Geometric(p_{sucess} = \frac{1000-i}{1000})$$ since it's getting harder and harder to fill more new boxes. And it's quite clear that this is a geometric process with probability of success being simply the proportion of empty box over the total number of box. Also the $X_i$ are independent since knowing the number of ball to transition from $x$ filled boxes to $x+1$ filled boxes doesn't change anything to the probability to transition from $y$ to $y+1$ filled boxes.

Let $Y$ be the number of ball throw to fill 980 boxes. $$ Y = \sum_{i=0}^{979} X_i,\hspace{1cm} n = \mathbb{E}[Y] = \sum_{i=0}^{979} \mathbb{E}[X_i] = \sum_{i=0}^{979} \frac{1}{\frac{1000-i}{1000}} = \sum_{i=0}^{979} \frac{1000}{1000-i} = 1000 (H_{1000} - H_{20}) $$ Where $H_n$ is the $n$-th harmonic number. The approximation using computer gives $n \approx 3887.7312$. However you can get a simpler estimate using the fact that $H_n \approx \ln(n)$ which tells you $n \approx 3912.02$.


Your Answer

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

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