Probability Question - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T22:18:44Z http://mathoverflow.net/feeds/question/8840 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/8840/probability-question Probability Question Claudiu 2009-12-14T04:21:21Z 2009-12-14T12:08:11Z <p>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?</p> <p>I came up with this formula:</p> <p>$\sum_{i=0}^{N}i\binom{N}{i}\left(\frac{N-i}{N}\right)^{M}$</p> <p>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.</p> http://mathoverflow.net/questions/8840/probability-question/8843#8843 Answer by Gjergji Zaimi for Probability Question Gjergji Zaimi 2009-12-14T04:45:29Z 2009-12-14T12:08:11Z <p>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}$</p> <p>EDIT: gave the answer in terms of M,N instead of the numerical values given originally...</p> http://mathoverflow.net/questions/8840/probability-question/8844#8844 Answer by Mike for Probability Question Mike 2009-12-14T05:06:57Z 2009-12-14T05:06:57Z <p>I wanted to give Claudiu some hints without spoiling it all. Oh well, Gjergji was faster... :)</p> <p>The important cookbook ingredients where:</p> <ol> <li>you only need to determine the expected value here;</li> <li><a href="http://en.wikipedia.org/wiki/Expected%5Fvalue#Linearity" rel="nofollow">Linearity of Expectation</a>;</li> <li>Possibly also <a href="http://en.wikipedia.org/wiki/E%5F%28mathematical%5Fconstant%29#Bernoulli%5Ftrials" rel="nofollow">asymptotics of $e$</a>.</li> </ol>