A total of $n$ balls, numbered $1$ through $n$, are put into $n$ urns, also numbered $1$ through $n$ in such a way that ball $i$ is equally likely to go into any of the urns $1, 2, . . . , i$. Find the expected number of urns that are empty.
Can somebody help me? I don´t understand.
Thanks very much.
On
We proceed by induction. For the case $n=1$, it is clear that the expected value of empty urns is $0$. Now, suppose that with $n$ urns our expected value, $E(n)$, is given by $(n-1)/2$.
For the case $n+1$, we can think of our procedure in two steps:
After step 1, there are on average $E(n)+1$ empty urns. As the last ball will end up in any urn with equal probability, there is a probability of $(E(n)+1)/(n+1)$ that our final ball will land in an empty urn. Subtracting, there remains a $(n-E(n))/(n+1)$ chance that the final ball will land in a previously-occupied urn. That is, our expected value on empty urns is given by
$$E(n+1)=E(n) \left(\frac{E(n)+1}{n+1}\right)+(E(n)+1)\left(\frac{n-E(n)}{n+1}\right)=\frac{n-1}{2}\cdot \frac{1}{2} + \frac{n+1}{2}\cdot \frac{1}{2},$$ in which we've used the inductive hypothesis $E(n)=(n-1)/2$. The right-hand side of the expression above is $n/2$, and this proves the $n+1$ case (so that we conclude by induction).
I'd like to point out that I would not have known how to formulate this induction without doing some cases by hand. I noticed that this pattern held for $n \leq 4$ before attempting the proof you see above.
Let $X$ be the number of empty urns. Then $X=X_1+X_2+\dots+X_n$ where $X_i$ is the indicator variable whose value is $1$ if the $i$th urn is empty, $0$ otherwise. Then $E(X_i)$ is the probability that the $i$th urn is empty, i.e., $E(X_i)=\frac{i-1}{i}\frac{i}{i+1}\frac{i+1}{i+2}\dots\frac{n-1}{n}=\frac{i-1}{n}$ (telescoping product). By linearity of expectation, $$E(X)=E(X_1)+\dots+E(X_n)=\frac{0}{n}+\frac{1}{n}+\frac{2}{n}+\dots+\frac{n-1}{n}=\frac{{n\choose 2}}{n}=\frac{n-1}{2}.$$