Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
Hint: Use the correct indicator function and linearity of expectation. –  cardinal Sep 20 '11 at 13:59
2  
In order to find the expected number of boxes with no balls, etc., you need to specify how the balls are placed in the boxes. For example, you tossed each ball towards the five boxes and each ball was equally likely to land in any of the five boxes, independent of past or future tosses; or you grabbed 0, 1, or 2 balls with equal probability and put them in the first, similarly for the second, etc., and the last box got all the remaining balls, if any. The answers for expected number of empty boxes will depend on the specification of the method. Please edit your question. –  Dilip Sarwate Sep 20 '11 at 14:02
    
@Dilip, you raise a good point, though to be fair to the OP, I'm guessing the "standard" assumptions for these problems apply (each ball independently goes into a bin selected uniformly at random). In any case, note that to compute the desired quantity, it is only necessary to know the marginal distribution of balls for each of the individual bins. :) –  cardinal Sep 20 '11 at 14:17
    
You may want to change the title of the question to avoid unwanted meanings in colloquial English. Currently it invites the answer "zero". See here and the "Slang dictionary" entry here. –  joriki Sep 20 '11 at 14:21
    
Poisson-binomial distribution is of direct relevance. –  Sasha Sep 20 '11 at 15:28
add comment

1 Answer

up vote 7 down vote accepted

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.

share|improve this answer
    
André, I don't think your answer is correct because the random variables are not independent of eachother. If box $X_1$ gets zero balls, than the other boxes are less likely to get zero balls. What this means is you can't separate $E[X]$ into the five $E[X_i]$'s. For example, with 3 boxes and 3 balls, there are ten possibilities: 003, 012, 021, 030, 102, 111, 120, 201, 210, 300. There are a total of 12 boxes with zero balls so $E[X] = 12/10 = 1.2$. This is not the same as the $3*(2/3)^3 = 8/9$ number we would get with your method. –  Rob Tanniru Feb 1 at 20:32
    
@Rob, Ten possibilities: 003, 012, 021, 030, 102, 111, 120, 201, 210, 300 are NOT equally likely. Having outcome 003 hasn't got the same probability as 012and so on –  user134278 Mar 9 at 22:18
1  
@RobTanniru: Indeed the random variables I used are not independent. However, the linearity of expectation holds whether or not the random variables we take a linear combination of are independent. It is that fact that accounts for a large part of the power of the technique. –  André Nicolas Jun 6 at 5:15
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.