# Sequential allocation of $n$ balls into $n$ urns

Assume that there are $n$ balls (numbered from $1$ to $n$) and $n$ urns (numbered from $1$ to $n$). At the beginning no ball is placed in any urn.

At $t=1$, each ball is randomly put into an urn (no restriction on how many balls an urn can contain, each ball can be placed into one urn for example) Check each urn and if there is more than one ball, randomly choose one of the balls and keep it in the urn and remove all the other balls. (do this for each urn)

At $t=2$, take the balls removed from some urn at $t=1$ and again randomly place into an urn (except the urn that the ball was removed from at $t=1$, say ball 1 was removed from urn 1, then ball 1 can be thrown at urns 2,3,...,n; same for other balls). Again, check each urn and if there is an urn that contains more than one ball and if there was no ball placed to that urn at $t=1$ choose one of them randomly and remove others. If there was a ball placed into that urn at $t=1$ remove all the new balls placed at $t=2$ from that urn.

At $t=k$, take the balls removed from some urn at $t=(k-1)$ and again randomly place into an urn ( except the urn that the ball was removed from at $t=1,...,(k-1)$). Again, check each urn and if there is an urn that contains more than one ball, choose one of them randomly if there was no ball placed to that urn at $t=1,\ldots,(k-1)$. If there was a ball placed into that urn at $t=1,\ldots,(k-1)$ remove all the new balls placed at $t=k$ from that urn.

Continue in this manner and stop when each urn has only one ball.

Although it should be clear, just to emphasize, if a ball is chosen to be placed into an urn at the end of $t=k$, it remains in that urn afterwards, that is, it can not be removed in the later stages. Also, a ball can not be thrown into an urn it was removed in earlier stages.

What is the probability that a certain ball, say Ball 1, is placed into some urn at exactly $t=k$ for each $k=1,\ldots,n$?

Any suggestions for the solution or even references on similar problems would be appreciated.

The answer for $t=1$ is easy: For example, consider Ball 1, and assume it is thrown into Urn 1 at $t=1$ and let $j$ be the number of balls that are placed into urn 1 at $t=1$ among the remaining $n-1$ balls. Then, probability that ball 1 is placed into urn 1 is:

$$\sum_{j=0}^{n-1}\binom{n-1}{j}\left( \frac{1}{n}\right) ^{j}\left( \frac{n-1}{n% }\right) ^{n-j-1}\left( \frac{1}{j+1% }\right)$$

-
I am a little unclear; at step t=1.5 when we are removing balls are these being removed from all urns with more than 1 ball or just 1? –  Dale M Apr 3 '13 at 9:22
Do this for each urn That has at least one ball: if there is only one ball, the ball is kept and if there are say 2 balls, choose one of them and remove so that there is only one ball left in the urn, if there are three balls remove 2 balls and so on. –  Emre Per Apr 3 '13 at 14:30
Your formula for $\mathbb{P}(t=1)$ simplifies to $1-\left({n-1\over n}\right)^n$. Otherwise, I don't believe you will get simple formulas. But I'll keep looking. –  Byron Schmuland Apr 5 '13 at 16:30
Thanks for looking. Yeah, I knew that but wanted to put this to give an idea how I proceed for solving the problem. I got the solution for $t=2$ also but stuck for above –  Emre Per Apr 5 '13 at 16:36

An approach: the thing to think about is how many urns are unoccupied after each run. The first ball that is put in an urn sticks and is never removed. After the first toss, on average $\frac 1e$ of the urns will be empty. That is also the number of balls thrown at urns in the second toss. The no repeat rule makes this a little messier as the empty urns are slightly more probable to receive a ball than the full ones. Ignoring that, each urn receives on average $\frac 1{e}$ balls, so the fraction of newly filled urns is $\frac 1e\exp(-\frac 1e)$, leaving about $0.255$ of the urns empty. After three tosses, the number of empty urns is $\frac 1e\exp(-\frac 1e)\exp(-\frac 1e\exp(-\frac 1e))\approx 0.197$. The chance that ball $1$ goes into some urn at turn $k$ is precisely the number of empty urns after turn $k-1$ as that is the number of balls that are not stuck. Again ignoring the no repeat rule, the chance ball $1$ goes in urn 1 at turn $k$ is then $\frac 1n$ (empty urns at turn $k-1$).

-
The approach is exactly what I was trying to follow but it is not easy to compute the expected number of empty urns. I do not think how you compute is true for the expected number of empty urns. –  Emre Per Apr 3 '13 at 18:22
@Emre Per: I am using the Poisson approximation, valid for lage $n$. Each ball arrives in a given urn with probability $\frac 1n$ and the probability of an urn being empty is $\exp(-\lambda)$ –  Ross Millikan Apr 3 '13 at 18:39

Let $\mathbb{U}_j$ be the random variable that a given ball that is "in play" (see below) $b$ is placed into urn $u$ at step $j$.

In the first instance, the probability mass function of $\mathbb{U}_1$ is

$$f_{\mathbb{U}_1}(k)=\begin{cases}\frac{1}{n} & \text{for k \in\{1,2,\ldots ,n\}}\\ 0 & \text{otherwise} \\\end{cases}$$

$$\mathbb{P}(\text{exactly } k \text{ urns are empty})={{n\choose n-k}{n \brace n-k}(n-k)!\over n^n}.$$

The notation ${n \brace n-k}$ refers to Stirling numbers of the second kind.

This allows you to create a random variable $\mathbb{X}_1$ that represents the number of empty urns at step $j=1$ and, importantly, the number of balls "in play" for step $j=2$.

$$f_{\mathbb{X}_1}(k)=\begin{cases}{{{n\choose n-k}{n \brace n-k}(n-k)!}\over {n^n}} & \text{for k \in\{1,2,\ldots ,n\}}\\ 0 & \text{otherwise} \\\end{cases}$$

So, $\frac{f_{\mathbb{X}_1}(k)}{n}$ is the probability a given ball is "in play" , and the probability that that ball will hit a given urn is $\frac{1}{n}$, so

\begin{align}f_{\mathbb{U}_2}(k)&=\frac{f_{\mathbb{X}_1}(k)(1-f_{\mathbb{U}_1}(k))}{n^2}\\ &=\begin{cases}{{n\choose n-k}{n \brace n-k}(n-k)!(n-1)\over n^{(n+3)}}& \text{for k \in\{1,2,\ldots ,n\}, k\ne u_1}\\ 0 & \text{otherwise} \\\end{cases} \end{align}

Removing the restriction that a ball cannot be placed in the same urn from which it was removed (which would be a fair approximation for large $n$), simplifies this to

\begin{align}f_{\mathbb{U}_2}(k)&=\frac{f_{\mathbb{X}_1}(k)}{n^2}\\ &=\begin{cases}{{n\choose n-k}{n \brace n-k}(n-k)!\over n^{(n+2)}}& \text{for k \in\{1,2,\ldots ,n\}}\\ 0 & \text{otherwise} \\\end{cases} \end{align}

The next step is to determine $\mathbb{X}_2$

It is clear that the number of balls in play is a monotonically decreasing function as once an urn has a ball it can never be empty again and this will end when each urn has one ball.

Now the $\mathbb{X}_1$ balls that are "in play" can be divided into $\mathbb{S}_1$ subsets with

\begin{align} f_{\mathbb{S}_1}(k)&= {{f_{\mathbb{X}_1}(k) \brace f_{\mathbb{X}_1}(k)-s}} \\ &=\begin{cases}{{n\choose n-k}{n \brace n-k}(n-k)!\over n^{n}} \brace {{{n\choose n-k}{n \brace n-k}(n-k)!\over n^{n}}-s}& \text{for k \in\{1,2,\ldots ,n\}, s\le k}\\ 0 & \text{otherwise} \end{cases}\end{align}

These subsets can be divided among the urns but now I'm stuck.

-