Expectation time for at least 2 balls in each bin

546 Views Asked by At

Given $N$ bins and an unlimited number of balls, to be assigned one ball per time unit to a uniformly random bin. What is the expected time to achieve at least 2 balls in every bin?

From a previous question Probability that all bins contain strictly more than one ball? we know the probability of failure (of at least one bit fewer than two balls) at time interval $t$ is given by
$$ F(t) = 1 - \frac{N!}{N^t} \sum_i (-1)^i \binom{t}{t-i} \left\{ t-i \atop N - i \right\} $$ (where the braces are expressing a Stirling number of the second kind). And much easier reasoning gives the expected time to first success (all bins having two or more balls) as $$ \begin{array}{l} \sum_t t \left[ (1-F(t)) - (1-F(t-1)) \right] \\ = \left[ (1-F(1)) - (1-F(0)) \right] +2\left[ (1-F(2)) - (1-F(1)) \right] + \ldots \\ = F(0) - F(1) + 2F(1) -2F(2) + 3F(2) -3F(3) +\ldots \\ = \sum_t \left( 1 - \frac{N!}{N^t} \sum_i (-1)^i \binom{t}{t-i} \left\{ t-i \atop N - i \right\} \right) \end{array} $$ But it is sometimes easier to get a simpler expression for an expectation value than to express the underlying distribution cleanly, so I am hopeful that this answer can be simplified.

1

There are 1 best solutions below

2
On BEST ANSWER

The expected number of tosses required to put at least 2 balls in each bin is $$\mathbb{E}(T)=\int_0^\infty 1-[1-(1+t/N)\exp(-t/N)]^N\,dt.$$ This can be proved by embedding your problem into a Poisson process.


Reference: Newman, Donald J.; Shepp, Lawrence (1960), "The double dixie cup problem", American Mathematical Monthly 67: 58–61.