My Math Forum (http://mymathforum.com/math-forums.php)

 Shanonhaliwell April 2nd, 2018 06:58 PM

Expected value

I had this question today in my midterm but I was not able to figure it out during the test. Can someone help me out?
There are n boxes numbered 1 to n and n balls numbered 1 to n. The balls are to be randomly placed in a box (not necessarily different boxes). What is the expected number of empty boxes?
Thank you.

 romsek April 2nd, 2018 10:25 PM

through listing the possible assignments and grinding out expectations I'm seeing the answer is

$E[\text{# empty boxes}] = \dfrac{(n-1)^n}{n^{n-1}}$

This is in very good agreement with sims for various $n$.

The assignments of boxes are uniform, each assignment having

$p=\left(\dfrac 1 n\right)^n$

The key is to transform the list of assignments into a count of empty boxes.

I don't yet recognize a simple formula that fits the data I generate for the individual probabilities of empty box counts.

Nevertheless using those to compute the expected value for various $n$ reveals the formula noted above.

I'm clearly missing something or this is just an impossible test question.

I'm sure the Peanut gallery will chime in.

 Shanonhaliwell April 3rd, 2018 09:43 PM

Quote:
 Originally Posted by romsek (Post 591269) through listing the possible assignments and grinding out expectations I'm seeing the answer is $E[\text{# empty boxes}] = \dfrac{(n-1)^n}{n^{n-1}}$ This is in very good agreement with sims for various $n$. The assignments of boxes are uniform, each assignment having $p=\left(\dfrac 1 n\right)^n$ The key is to transform the list of assignments into a count of empty boxes. I don't yet recognize a simple formula that fits the data I generate for the individual probabilities of empty box counts. Nevertheless using those to compute the expected value for various $n$ reveals the formula noted above. I'm clearly missing something or this is just an impossible test question. I'm sure the Peanut gallery will chime in.
I think the $p=\left(\dfrac 1 n\right)^n$ is the probability a box is not empty after all balls are thrown.
This is how I try to do, let me know if I have done it wrong.
Here, for each $i=1,2,\cdots,n$ define the random variable
$X_i=\begin{cases} 1 &\text{if the i^{\rm th} box is empty} \\ 0 &\text{otherwise} \\ \end{cases}$

Now let $X$ be the total number of empty boxes. Then the number of empty boxes is $X=\sum\limits_{i=1}^n X_i=X_1+X_2+\cdots+X_n$ and the expected number is $E(X)=\sum\limits_{i=1}^{n}E(X_i)=E(X_1) + E(X_2) + \cdots + E(X_n)$ (Using the linearity of expectation).

Each time a ball is thrown, the probability a ball lands in that one box is $\dfrac{1}{n}$ so there is a $\dfrac{n-1}{n}$ chance that it will not land in that box. So the probability that particular box remains empty after all the balls are thrown is $\left(\dfrac{n-1}{n}\right)^n$, since this event must occur n times as we have n balls. Hence, $E(X_i)=P(X_i=1)=\left(\dfrac{n-1}{n}\right)^n$.
$E[\text{number of empty boxes}]=\sum\limits_{i=1}^{n} E(X_i)=n\cdot E(X_i)=n\cdot \left(\dfrac{n-1}{n}\right)^n = \dfrac{(n-1)^n}{n^{n-1}}$

 romsek April 3rd, 2018 10:58 PM

Quote:
 Originally Posted by Shanonhaliwell (Post 591332) Thank you @romsek.You answer is so helpful. I think the $p=\left(\dfrac 1 n\right)^n$ is the probability a box is not empty after all balls are thrown. This is how I try to do, let me know if I have done it wrong. Here, for each $i=1,2,\cdots,n$ define the random variable $X_i=\begin{cases} 1 &\text{if the i^{\rm th} box is empty} \\ 0 &\text{otherwise} \\ \end{cases}$ Now let $X$ be the total number of empty boxes. Then the number of empty boxes is $X=\sum\limits_{i=1}^n X_i=X_1+X_2+\cdots+X_n$ and the expected number is $E(X)=\sum\limits_{i=1}^{n}E(X_i)=E(X_1) + E(X_2) + \cdots + E(X_n)$ (Using the linearity of expectation). Each time a ball is thrown, the probability a ball lands in that one box is $\dfrac{1}{n}$ so there is a $\dfrac{n-1}{n}$ chance that it will not land in that box. So the probability that particular box remains empty after all the balls are thrown is $\left(\dfrac{n-1}{n}\right)^n$, since this event must occur n times as we have n balls. Hence, $E(X_i)=P(X_i=1)=\left(\dfrac{n-1}{n}\right)^n$. $E[\text{number of empty boxes}]=\sum\limits_{i=1}^{n} E(X_i)=n\cdot E(X_i)=n\cdot \left(\dfrac{n-1}{n}\right)^n = \dfrac{(n-1)^n}{n^{n-1}}$
outstanding, you seem to be getting the hang of things.

 Shanonhaliwell April 8th, 2018 03:31 PM

Quote:
 Originally Posted by romsek (Post 591335) outstanding, you seem to be getting the hang of things.
Thanks to you, I was able to do it.

 All times are GMT -8. The time now is 12:30 AM.