# Expectation and Variance, number of balls

Question:

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 ...

• 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"? – John Jun 17 '13 at 18:27
• $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]$ – 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.