4
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Theo Johnson-Freyd
    Commented Dec 14, 2009 at 6:08
  • $\begingroup$ What is nonintuitive about the question? $\endgroup$
    – José Figueroa-O'Farrill
    Commented Dec 14, 2009 at 6:48
  • $\begingroup$ 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. $\endgroup$
    – Claudiu
    Commented Dec 14, 2009 at 8:46

2 Answers 2

Reset to default
5
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ I was thinking of something along these lines, but doesn't it matter that the Xi variables are not independent? $\endgroup$
    – Claudiu
    Commented Dec 14, 2009 at 4:50
  • $\begingroup$ @Claudiu: The Xi's are not independent but they are identically distributed (symmetry). Also note that expectation is always linear. $\endgroup$
    – Gjergji Zaimi
    Commented Dec 14, 2009 at 4:56
  • $\begingroup$ 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. $\endgroup$
    – Claudiu
    Commented Dec 14, 2009 at 11:50
  • 1
    $\begingroup$ 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 ;) $\endgroup$
    – Gjergji Zaimi
    Commented Dec 14, 2009 at 12:06
4
$\begingroup$

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$.
Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .