how to find the expected number of boxes with no balls

If you have 10 balls and 5 boxes what is the expected number of boxes with no balls. The probability that each ball goes independently into box $i$ is $p_i$ with the $\sum_{i=1}^5 p_i =1$. Also, what is the expected number of boxes that have exactly one ball. For part 1, isn't the answer related to the number of solutions to the equation $x_1+x_2+x_3+x_4+x_5 = 10$ where all the $x$s can take on nonnegative integers? And for the second part, isn't it the number of only positive solutions?

Solution 1:

We first describe informally the probability model. We grab the first ball, and choose at random a box to put this ball into, with all choices equally likely. We then independently go through the same procedure with the second ball, the third ball, and so on.

Expected Number of Empty Boxes: For $i=1, 2, \dots, 5$, define the random variable $X_i$ by $X_i=1$ if Box $i$ ends up with zero balls, and by $X_i=0$ otherwise. Let $$X=X_1+X_2+X_3+X_4+X_5.$$ Then $X$ is the total number of boxes that end up with zero balls in them. Note that $$E(X)=E(X_1+X_2+\cdots+X_5)=E(X_1)+E(X_2)+\cdots+E(X_5).$$ Next we calculate $E(X_i)$. For any $i$, $X_i=1$ if $10$ times in a row we chose one of the other boxes. Thus $P(X_i=1)=(4/5)^{10}$. It follows that $$E(X_i)=\left(\frac{4}{5}\right)^{10}.$$ Now the calculation of $E(X)$ is easy: $$E(X)=5\left(\frac{4}{5}\right)^{10}.$$

Expected Number with $1$ Ball: The same idea works. Let random variable $Y_i$ have value $1$ if Box $i$ ends up with $1$ ball, and value $0$ otherwise. Let $Y=Y_1+Y_2+\cdots+Y_5$. Then $Y$ is the number of boxes with precisely $1$ ball. We want $E(Y)$.

The probability that Box $i$ has precisely one ball is given by $$P(Y_i=1)=\binom{10}{1}\left(\frac{1}{5}\right)^1\left(\frac{4}{5}\right)^9.$$ Then $E(Y_i)=P(Y_i=1)$, and $E(Y)=5E(Y_i)$.

Comment: We could in principle deal with the first question by finding the probability distribution function of the random variable $X$, and then using the ordinary expression for expectation. Similarly, we could find the probability distribution function of the random variable $Y$. But the probability distribution functions are a little bit tricky to compute. The (standard) procedure that we used bypasses the problem of finding these distributions. It is a very powerful technique, with many applications.

Solution 2:

The easiest method to use to solve this problem is to find the sum of the expectation of random variables, as André Nicolas has already shown. I would just like to add one minor point: the problem actually does not state that the probabilities are equal. It says only that the sum of the probabilities is 1.

Using the method of taking the sum of random variables, let us do the first part of the problem. Let our experiment involve dropping all ten balls into the five boxes. We use an indicator random variable $X_i, i = 1, 2, 3, 4, 5$, where $X = 1$ if box $i$ is empty (this is a success) and $X = 0$ if it is not (this is a failure). $E[X_i] = 1*(1 - p_i)^{10}$, and there are five boxes, so $E[X] = \sum\limits_{i = 1}^{5}(1 - p_i)^{10}$.

It bears repeating that this method does not require independence, as André Nicolas has also pointed out above.

Solution 3:

Here's a more intuitive perspective using induction/recursion (it also solves the general problem with $m$ balls and $n$ boxes).

There are 5 boxes. You want to know the expected number of empty boxes when there are 10 balls. Key insight: If you knew the answer for $(\text{balls}, \text{boxes}) = (9, 5)$, then you'd be done! Why? Let $$E_m = \text{expected number of empty boxes for $m$ balls and $5$ boxes}.$$ On average, $E_9$ boxes will be empty after you've placed the first nine balls. Now, the last ball must be placed in an empty box or a non-empty box. The probability of placing it in an empty box is $E_9/5$ because, well, there are $E_9$ empty boxes out of the $5$. Thus, $E_9/5$ of the time, you'll have $E_9 - 1$ empty boxes; the rest of the time, you'll have $E_9$ empty boxes, that is, $$E_{10} = \frac{E_9}5(E_9-1) + \left(1-\frac{E_9}5\right) E_9 = \frac45E_9.$$ Another way to say the same thing: After placing the first nine balls, you have $E_9$ empty boxes; there's a $E_9/5$ chance you'll have one fewer empty box after placing the last ball: $$E_{10} = E_9 + \frac{E_9}5(-1) = \frac45E_9.$$ There's, of course, nothing special about $10$ or $9$; the same argument yields $$E_m = \frac45E_{m-1}.$$ Since $E_0 = 5$ (this is trivial; or if you prefer, $E_1 = 4$ is also trivial), we conclude that $$E_m = \left(\frac45\right)^m5.$$ Obviously, there's nothing special about $5$ either. For $m$ balls and $n$ boxes, we have $$E_{m,n} = \text{expected number of empty boxes for $m$ balls and $n$ boxes} = \left(\frac{n-1}n\right)^mn.$$