how to find the expected number of boxes with no balls
up vote
10
down vote
favorite
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?
probability
add a comment |
up vote
10
down vote
favorite
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?
probability
3
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
1
@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 a comment |
up vote
10
down vote
favorite
up vote
10
down vote
favorite
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?
probability
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?
probability
probability
edited Sep 20 '11 at 15:18
user940
asked Sep 20 '11 at 13:51
lord12
86542040
86542040
3
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
1
@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 a comment |
3
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
1
@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
3
3
Hint: Use the correct indicator function and linearity of expectation.
– cardinal
Sep 20 '11 at 13:59
Hint: Use the correct indicator function and linearity of expectation.
– cardinal
Sep 20 '11 at 13:59
2
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
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
1
1
@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
@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
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
Poisson-binomial distribution is of direct relevance.
– Sasha
Sep 20 '11 at 15:28
add a comment |
3 Answers
3
active
oldest
votes
up vote
13
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)=5left(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)^1left(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.
1
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 '14 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 '14 at 22:18
2
@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 '14 at 5:15
@RobTanniru Your method works well when the balls are indistinguishable and boxes are distinguishable but here we are taking both as distinguishable. Don't assume those things unless the question strictly says so. Take a note what André Nicolas said.
– ViX28
Jul 2 '17 at 8:47
@ViX28, I don't understand how you conclude that the balls are distinguishable here. If every ball is placed into a box independently and with the same probabilities, then how could you distinguish if a ball in a box was the first or second ball for example. This is why I think $P(Y_i=1) = p_i*(1-p_i)^9$, there is no difference which order the ball went into bin i, the final state will have a single ball. Correct me if I'm wrong?
– Filip
Jun 9 at 20:05
add a comment |
up vote
1
down vote
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] = sumlimits_{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.
add a comment |
up vote
0
down vote
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}5right) 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(frac45right)^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}nright)^mn.$$
add a comment |
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
13
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)=5left(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)^1left(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.
1
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 '14 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 '14 at 22:18
2
@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 '14 at 5:15
@RobTanniru Your method works well when the balls are indistinguishable and boxes are distinguishable but here we are taking both as distinguishable. Don't assume those things unless the question strictly says so. Take a note what André Nicolas said.
– ViX28
Jul 2 '17 at 8:47
@ViX28, I don't understand how you conclude that the balls are distinguishable here. If every ball is placed into a box independently and with the same probabilities, then how could you distinguish if a ball in a box was the first or second ball for example. This is why I think $P(Y_i=1) = p_i*(1-p_i)^9$, there is no difference which order the ball went into bin i, the final state will have a single ball. Correct me if I'm wrong?
– Filip
Jun 9 at 20:05
add a comment |
up vote
13
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)=5left(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)^1left(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.
1
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 '14 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 '14 at 22:18
2
@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 '14 at 5:15
@RobTanniru Your method works well when the balls are indistinguishable and boxes are distinguishable but here we are taking both as distinguishable. Don't assume those things unless the question strictly says so. Take a note what André Nicolas said.
– ViX28
Jul 2 '17 at 8:47
@ViX28, I don't understand how you conclude that the balls are distinguishable here. If every ball is placed into a box independently and with the same probabilities, then how could you distinguish if a ball in a box was the first or second ball for example. This is why I think $P(Y_i=1) = p_i*(1-p_i)^9$, there is no difference which order the ball went into bin i, the final state will have a single ball. Correct me if I'm wrong?
– Filip
Jun 9 at 20:05
add a comment |
up vote
13
down vote
accepted
up vote
13
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)=5left(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)^1left(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.
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)=5left(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)^1left(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.
edited Sep 21 '11 at 5:41
answered Sep 20 '11 at 15:12
André Nicolas
450k36419803
450k36419803
1
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 '14 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 '14 at 22:18
2
@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 '14 at 5:15
@RobTanniru Your method works well when the balls are indistinguishable and boxes are distinguishable but here we are taking both as distinguishable. Don't assume those things unless the question strictly says so. Take a note what André Nicolas said.
– ViX28
Jul 2 '17 at 8:47
@ViX28, I don't understand how you conclude that the balls are distinguishable here. If every ball is placed into a box independently and with the same probabilities, then how could you distinguish if a ball in a box was the first or second ball for example. This is why I think $P(Y_i=1) = p_i*(1-p_i)^9$, there is no difference which order the ball went into bin i, the final state will have a single ball. Correct me if I'm wrong?
– Filip
Jun 9 at 20:05
add a comment |
1
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 '14 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 '14 at 22:18
2
@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 '14 at 5:15
@RobTanniru Your method works well when the balls are indistinguishable and boxes are distinguishable but here we are taking both as distinguishable. Don't assume those things unless the question strictly says so. Take a note what André Nicolas said.
– ViX28
Jul 2 '17 at 8:47
@ViX28, I don't understand how you conclude that the balls are distinguishable here. If every ball is placed into a box independently and with the same probabilities, then how could you distinguish if a ball in a box was the first or second ball for example. This is why I think $P(Y_i=1) = p_i*(1-p_i)^9$, there is no difference which order the ball went into bin i, the final state will have a single ball. Correct me if I'm wrong?
– Filip
Jun 9 at 20:05
1
1
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 '14 at 20:32
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 '14 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 '14 at 22:18
@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 '14 at 22:18
2
2
@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 '14 at 5:15
@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 '14 at 5:15
@RobTanniru Your method works well when the balls are indistinguishable and boxes are distinguishable but here we are taking both as distinguishable. Don't assume those things unless the question strictly says so. Take a note what André Nicolas said.
– ViX28
Jul 2 '17 at 8:47
@RobTanniru Your method works well when the balls are indistinguishable and boxes are distinguishable but here we are taking both as distinguishable. Don't assume those things unless the question strictly says so. Take a note what André Nicolas said.
– ViX28
Jul 2 '17 at 8:47
@ViX28, I don't understand how you conclude that the balls are distinguishable here. If every ball is placed into a box independently and with the same probabilities, then how could you distinguish if a ball in a box was the first or second ball for example. This is why I think $P(Y_i=1) = p_i*(1-p_i)^9$, there is no difference which order the ball went into bin i, the final state will have a single ball. Correct me if I'm wrong?
– Filip
Jun 9 at 20:05
@ViX28, I don't understand how you conclude that the balls are distinguishable here. If every ball is placed into a box independently and with the same probabilities, then how could you distinguish if a ball in a box was the first or second ball for example. This is why I think $P(Y_i=1) = p_i*(1-p_i)^9$, there is no difference which order the ball went into bin i, the final state will have a single ball. Correct me if I'm wrong?
– Filip
Jun 9 at 20:05
add a comment |
up vote
1
down vote
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] = sumlimits_{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.
add a comment |
up vote
1
down vote
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] = sumlimits_{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.
add a comment |
up vote
1
down vote
up vote
1
down vote
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] = sumlimits_{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.
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] = sumlimits_{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.
answered Dec 1 '15 at 22:39
Vadim Dukhovny
112
112
add a comment |
add a comment |
up vote
0
down vote
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}5right) 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(frac45right)^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}nright)^mn.$$
add a comment |
up vote
0
down vote
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}5right) 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(frac45right)^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}nright)^mn.$$
add a comment |
up vote
0
down vote
up vote
0
down vote
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}5right) 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(frac45right)^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}nright)^mn.$$
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}5right) 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(frac45right)^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}nright)^mn.$$
answered Nov 20 at 1:52
whippedcream
39416
39416
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f66077%2fhow-to-find-the-expected-number-of-boxes-with-no-balls%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
3
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
1
@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