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$
$\endgroup$
6
2 Answers
$\begingroup$
$\endgroup$
3
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$ Jun 20, 2013 at 7:39
-
$\begingroup$ @Bloodmoon- I don't understand. I have arrived at the probability itself from combinatorics! $\endgroup$– user67803Jun 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$ Dec 2, 2016 at 22:41
$\begingroup$
$\endgroup$
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}$
Ldenote 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 aBayes formula. Does it analysis make sense? $\endgroup$