Probability Question - MathOverflow

Probability Question

2009-12-14T04:21:21Z

You have $N$ boxes and $M$ balls. The $M$ balls are randomly distributed into the $N$ boxes. What is the expected number of empty boxes?

I came up with this formula:

$\sum_{i=0}^{N}i\binom{N}{i}\left(\frac{N-i}{N}\right)^{M}$

This seems to yield the right answer. However, it requires calculating large numbers, such as $\binom{N}{\frac{N}{2}}$. Is there a more direct way, perhaps using a probability distribution? It seems that neither the binomial nor the hypergeometric distributions fit the problem.

Answer by Gjergji Zaimi for Probability Question

2009-12-14T04:45:29Z

Let $X_i$ be a random variable with value 1 when box $i$ is empty and 0 otherwise. Now $P(X_i=1)=(1-\frac{1}{N})^{M}$. And the expected number of empty boxes is just $\mathbb{E}(\sum X_i)=N\mathbb{E}(X_1)\approx \frac{N}{e^M}$

EDIT: gave the answer in terms of M,N instead of the numerical values given originally...

Answer by Mike for Probability Question

2009-12-14T05:06:57Z

I wanted to give Claudiu some hints without spoiling it all. Oh well, Gjergji was faster... :)

The important cookbook ingredients where:

you only need to determine the expected value here;
Linearity of Expectation;
Possibly also asymptotics of $e$.