n boxes are ordered in a row on a table , labeled 1 to n. In every box there's a ball. In every step Nicole chooses a ball randomly (in uniform distribution) , puts it out of the box, then chooses a box and puts the ball in it (again, in uniform distribution, between the n boxes). $X_1$ is the the number of balls in box number 1 on the 37th step.

What is $E[X_1], V[X_1]$

Thoughts: I understood the solution is 1 for both, from "symmetry", But when i try to calculate them formally (using the definition of expectation), It doesn't work out ...

  • $\begingroup$ I suspect V[X_1] tends to 1 as the number of steps tends to infinity, but would be a bit surprised if it were identically 1 o the 37th step. Can you show us what you've tried "formally"? $\endgroup$ – John Jun 17 '13 at 18:27
  • $\begingroup$ $V(X1)=E[X_1^2]-E^2[X_1]= 1 \frac {n^2-2n+2}{n^2}+4 \frac {n-1}{n^2} -1 \ne 1$ (I took the same probabilities for which I calculated $E[X_1]$ and used them to calculate $E[X_1^2]$ $\endgroup$ – jreing Jun 17 '13 at 18:30

Each ball starts in one of the boxes; think of the ball that starts in box $j$ as "ball $j$". Write $$ X_1=\sum_{j=1}^{n}1_{\{\text{Ball $j$ is in box 1 after 37 steps}\}}. $$ What is $P(\text{Ball $j$ is in box 1 after 37 steps})$?

If $j\neq 1$, then $$ P(\text{Ball $j$ is in box 1 after 37 steps})=\left(1-\left(1-\frac{1}{n}\right)^{37}\right)\cdot\frac{1}{n}. $$ Why? For ball $j$ to end in box 1, it must have been chosen at least once; the probability that this happens is the first term. Once we know ball $j$ has been chosen at least once, its position is uniformly random, hence the $\frac{1}{n}$. This is true for all $j\neq 1$; for $j=1$, we have $$ P(\text{Ball $1$ is in box 1 after 37 steps})=\left(1-\frac{1}{n}\right)^{37}+\left(1-\left(1-\frac{1}{n}\right)^{37}\right)\cdot\frac{1}{n}; $$ the second term is just like before, while the first term corresponds to the possibility that ball 1 has never been chosen - which leaves it in box 1.

Breaking up $\mathbb{E}[X_1]$ over summation, we have $$ \mathbb{E}[X_1]=\left(1-\frac{1}{n}\right)^{37}+\left(1-\left(1-\frac{1}{n}\right)^{37}\right)=1, $$ as you claimed.

Try using these same indicators to compute $\mathbb{E}[X_1^2]$ (or, even better, $\mathbb{E}[X_1(X_1-1)]$) to get at the variance.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.