A total of $n$ balls, numbered $1,\ldots,n$, are put into $n$ urns, also numbered $1,\ldots,n$, in such a way that the $i$th ball is equally likely to go into any of the urns $1,\ldots,i$. What is the expected number of empty urns? What is the probability that none of the urns are empty?
Let $X_i=1$ if the $i$th urn is empty, and $X_i=0$ otherwise. Then $X=\sum_{i=1}^nX_i$ counts the number of empty urns. Since the $j$th ball must choose any of its possible urns but the empty one,
$$P[X_i=1]=\prod_{j=i}^n\frac{j-1}{j}$$
hence,
$$E[X]=\sum_{i=1}^nE[X_i]=\sum_{i=1}^n\prod_{j=i}^n\frac{j-1}{j}$$
Is this work for the first part correct? If no, then where did I go wrong? If yes, then does the expression above converge to any elementary closed-form algebraic expression?
Then, how should I approach the second part of the question, since I'm lost on approach?
Best Answer
(1) I think your value for $P(X_i=1)$ is not right. I think it should be $\left(\dfrac{n-1}{n}\right) ^n$ because each of the $n$ balls has probability $\dfrac{n-1}{n}$ of not being in Urn $i$ (independently of the other balls). So,
\begin{eqnarray*} E(X) &=& \sum_{i=1}^n E(X_i) \\ &=&nE(X_1) \qquad\qquad\qquad\qquad\text{since all $X_i$ are identically distributed} \\ &=& nP(X_1=1) \\ &=& n\left( \dfrac{n-1}{n}\right) ^n. \end{eqnarray*}
(2)
Suppose we number the balls $1,\ldots,n$. An arrangement where there is one ball in every urn is just a permutation of the $n$ balls. The number of such permutations is $n!$.
The total number of arrangements of $n$ balls in $n$ urns is $n^n$ because for each ball there is a choice of $n$ urns. Therefore,
\begin{eqnarray*} P(\text{No urns are empty}) &=& \dfrac{\text{#permutations of $n$ numbers}}{\text{#arrangements of $n$ balls in $n$ urns}} = \dfrac{n!}{n^n}. \end{eqnarray*}