6
$\begingroup$

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?

$\endgroup$
6
  • $\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

6
$\begingroup$

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}}}}$

$\endgroup$
3
  • $\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
2
$\begingroup$

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}$

$\endgroup$

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.