Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
I was not one of the down votes, but I'll make a stab at why they're there. The aesthetic at MO seems to be to avoid specific numbers in problems: they make the problem look too homework-y. Instead, you could ask the the expected number of empty boxes when $N$ balls are assigned randomly to $M$ boxes, as a function of $N,M$. It's still not a deep question, as far as I can tell, and would be much better if you also waved at why you care about the question. –  Theo Johnson-Freyd Dec 14 '09 at 6:08
    
What is nonintuitive about the question? –  José Figueroa-O'Farrill Dec 14 '09 at 6:48
    
It was non-intuitive to me, but that is subjective, so I've removed the tag. I just didn't realize to break the problem down into more than one random variable. Thank you Theo for the tips as well. –  Claudiu Dec 14 '09 at 8:46
add comment

2 Answers

up vote 3 down vote accepted

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...

share|improve this answer
    
I was thinking of something along these lines, but doesn't it matter that the Xi variables are not independent? –  Claudiu Dec 14 '09 at 4:50
    
@Claudiu: The Xi's are not independent but they are identically distributed (symmetry). Also note that expectation is always linear. –  Gjergji Zaimi Dec 14 '09 at 4:56
    
Your answer is one of the terms of my answer. Is my answer simply incorrect, then? If so, can you explain why? It makes sense to me that it would work. –  Claudiu Dec 14 '09 at 11:50
1  
Claudiu note that the i'th term in your sum (after division by i) gives the probability of there being AT LEAST i empty boxes and doesn't guarantee there being exactly i empty boxes. With your approach you'd have to subtract some terms ;) –  Gjergji Zaimi Dec 14 '09 at 12:06
add comment

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

The important cookbook ingredients where:

  1. you only need to determine the expected value here;
  2. Linearity of Expectation;
  3. Possibly also asymptotics of $e$.
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.