I have a very brief question: if I put $M$ balls into $N$ boxes at random, what is the average number of balls in the boxes that are not empty?

  • $\begingroup$ It may not be easy. Let $T$ be the number of non-empty boxes. The mean of $T$ can be found, but that does not tell us the mean of $\frac{1}{T}$. $\endgroup$ Jun 20, 2013 at 6:24
  • $\begingroup$ Can we think about this question from the angle of probability, rather than combinatorics? Let L denote the number of balls in the boxes that are not empty. E[L]=sum_{l=1}^{l=M}P{L=l}*l. Because we want to count the boxes that are not empty, P{L=l} should be derived from a Bayes formula. Does it analysis make sense? $\endgroup$
    – Bloodmoon
    Jun 20, 2013 at 6:37
  • $\begingroup$ A complicated expression for the probabilities can be found. Too messy to evaluate $E(1/T)$. There is, however, a trick for finding $E(T)$. $\endgroup$ Jun 20, 2013 at 6:41
  • $\begingroup$ what is that trick? $\endgroup$
    – Bloodmoon
    Jun 20, 2013 at 7:55
  • $\begingroup$ The answers so far are wrong. I still have to see the correct probability distribution of the number $X$ of nonempty boxes. $\endgroup$ Jun 20, 2013 at 8:23

2 Answers 2


Let $A$ be the number of non-empty boxes. Then the average number of balls in each box=$\displaystyle{\frac{M}{A}}$.

In random distribution, the value of $A$ may vary.

Probability of $A$ boxes being selected= $\displaystyle{\frac{\binom{N}{A}}{\binom{N}{1}+\binom{N}{2}+\dots \binom{N}{M}}}$

Hence, expected value of average=$\displaystyle{\sum_{A=1}^{M} \frac{M}{A}.{\frac{\binom{N}{A}}{\binom{N}{1}+\binom{N}{2}+\dots \binom{N}{M}}}}$

  • $\begingroup$ It's awesome! This answer is derived from the combinatorics, could you please analyze from the angle of probability? Please have a look at my comment beneath the question post. Thank you so much! $\endgroup$
    – Bloodmoon
    Jun 20, 2013 at 7:39
  • $\begingroup$ @Bloodmoon- I don't understand. I have arrived at the probability itself from combinatorics! $\endgroup$
    – user67803
    Jun 20, 2013 at 16:41
  • $\begingroup$ If anyone still cares, having perused this answer for my own study, should the denominator in the probability of $A$ boxes being selected end with ${N\choose N}$ instead of ${N\choose M}$? $\endgroup$
    – The Count
    Dec 2, 2016 at 22:41

Let $X$ denotes the number of non-empty boxes.

Then $P(X=r)={N\choose r}\left(\frac{1}{2}\right)^r\left(\frac{1}{2}\right)^{N-r}={N\choose r}\left(\frac{1}{2}\right)^N$ (assuming binomial distribution)

Let $E(Y)$ denotes the average number of balls in non-empty boxes,

then , $E(Y)|(X=r)=\frac{M}{r}$ (assuming uniform distribution of balls in non-empty boxes)

Then $E(Y)=\sum_{r=1}^NP(X=r)E(Y)|(X=r)=\frac{M}{2^N}\sum_{r=1}^N\frac{{N\choose r}}{r}$


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .