My Math Forum

My Math Forum (http://mymathforum.com/math-forums.php)
-   Advanced Statistics (http://mymathforum.com/advanced-statistics/)
-   -   Expected value (http://mymathforum.com/advanced-statistics/343833-expected-value.html)

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.

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}}
\]

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.

Copyright © 2019 My Math Forum. All rights reserved.