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