$n$ balls into $n$ urns until there is no empty urn.

Question

We have $n$ balls and $n$ urns.

Step 1. Throw $n$ balls into $n$ urns randomly.

Check each urn and if there is more than one ball in an urn, choose only one and keep in the urn and remove all the other balls.

Step 2. Suppose there are $k$ balls ''not placed'' in an urn in Step 1. Throw these $k$ balls into the urns randomly.

And move on in this fashion until there is no empty urn.

What is the expected number of urns that are empty in each step?

Answer. Step 1 is easy. For any urn $u_{j}$, define $X_{j}$ as $X_{j}=1$ if no ball hits and $X_{j}=0$, otherwise. Then, expected number of empty urns is just $E(X)$ where $X=X_{1}+X_{2}+...+X_{n}$. Note that $E(X_{j})=Pr(X_{j}=1)=(\frac{n-1}{n})^n$. Hence, $E(X)=n(\frac{n-1}{n})^n$.

After Step 1, things get complicated. A heuristic approach for Step 2: The expected number of empty urns (and hence unplaced balls) is just $n(\frac{n-1}{n})^n$. Thus, for large $n$, the expected number of empty urns in Step 2 is $n\left( \frac{n-1}{n}\right) ^{n}\left( \frac{n-1}{n}\right) ^{n\left(\frac{n-1}{n}\right) ^{n}}$ (within some bound?)

Is this approach correct? Can this be made rigorous?

Answer 1

Let label the states with the number of the filled urns. Our aim is to find the probability of transition from the state $m$ to the state $l$ ($0\le m\le l\le n$). This probability is: $$\begin{align} P_{ml}(n)&=\frac1{n^{n-m}}\binom{n-m}{l-m} \sum_{i=l-m}^{n-m}\binom{n-m}i(l-m)!{i \brace l-m}m^{n-m-i}\\ &=\frac1{n^{n-m}}\frac{(n-m)!}{(n-l)!} \sum_{i=l-m}^{n-m}\binom{n-m}i{i \brace l-m}m^{n-m-i},\tag1 \end{align}$$ where the symbols count the following numbers of way:

1. $n^{n-m}$ - to place $n-m$ balls into $n$ urns;
2. $\binom{n-m}{l-m}$ - to choose $l-m$ "active" urns to be filled out of $n-m$ empty ones;
3. $\binom{n-m}i$ - to choose $i$ balls out of $n-m$ ones;
4. $(l-m)!{i \brace l-m}$ - to place $i$ balls into $l-m$ "active" urns in such a way that there is at least one ball in each of these urns. Here ${i \brace l-m}$ is the Stirling number of second kind;
5. $m^{n-m-i}$ - to place the rest balls into $m$ already filled urns.

After the transition matrix $P(n)$ is constructed the expected value of the empty urns after $k$ steps can be computed as: $$ \mathsf E_k(n)=n-\sum_{i=1}^n i[P^k(n)]_{0i}.\tag2 $$

---

Example.

For $n=5$ one obtains:

$$P(5)=\left(\begin{array}{cccccc} 0 & \frac{1}{625} & \frac{12}{125} & \frac{12}{25} & \frac{48}{125} & \frac{24}{625} \\ 0 & \frac{1}{625} & \frac{12}{125} & \frac{12}{25} & \frac{48}{125} & \frac{24}{625} \\ 0 & 0 & \frac{8}{125} & \frac{57}{125} & \frac{54}{125} & \frac{6}{125} \\ 0 & 0 & 0 & \frac{9}{25} & \frac{14}{25} & \frac{2}{25} \\ 0 & 0 & 0 & 0 & \frac{4}{5} & \frac{1}{5} \\ 0 & 0 & 0 & 0 & 0 & 1 \\\end{array}\right).$$

The corresponding values $\mathsf E_k (5)$ for $k=1,\dots,10$ are respectively: $$ \begin{array}{l} 1.6384 \\ 1.07168 \\ 0.782347 \\ 0.599572 \\ 0.470231 \\ 0.372795 \\ 0.297015 \\ 0.237173 \\ 0.18958 \\ 0.151607 \\\end{array} $$

---

One can easily demonstrate that the 0th and the 1st rows of the transition matrix are identical, and the 0th column is $0$. Therefore one can for the sake of simplicity drop the 0th row and column from the matrix, so that $1\le m,l\le n$ in (1). The only required change after the redefinition of $P(n)$ is to replace the index $0i $ in the formula (2) with $1i $.