Hyper Birthday Paradox?

There are $N$ buckets.

Each second we add one new ball to a random bucket - so at $t=k$, there are a total of $k$ balls collectively in the buckets.

At $t=1$, we expect that at least one bucket contains one ball.

At $t=\sqrt{2N\ln{2}}$, due to birthday paradox, we expect that at least one bucket contains two balls.

.

.

At $t=f(m)$, we expect at least one bucket to contain $m$ balls.

What is the function $f(m)$?

Solution 1:

Firstly, for $m = 2$, the expected time $f(2)$ at which at least one bucket contains two balls is not $t = \sqrt{2N\ln 2}$. That is the time $t$ at which the probability that there is at least one bucket with two balls crosses $\frac12$. The actual expected time $t$ at which at least one bucket contains two balls is instead given by $$\begin{align} 1 + Q(N) &= 1 + 1 + \frac{N-1}{N} + \frac{(N-1)(N-2)}{N^2} + \cdots + \frac{(N-1)(N-2) \cdots 1}{N^{N-1}} \\ &\sim \sqrt{\frac{\pi N}{2}} + \frac{1}{3}+\frac{1}{12}\sqrt{\frac{\pi}{2N}}-\frac{4}{135N}+\cdots \end{align} $$ where the $\sim$ denotes that these are the precise asymptotics.

(Mildly related: this question and the methods of asymptotic analysis at this one.)

For $m = 3$, see this question, where it is shown that the answer is $$ f(3) = \int_0^\infty \left(1+{x\over N}+{x^2\over2N^2}\right)^N \,e^{-x}\,dx $$ which has asymptotics $$ f(3) \sim 6^{1/3}\,\Gamma(4/3)\, N^{2/3} \approx 1.6226\,N^{2/3}. $$

For general $m$, the above question also says that the above answer generalizes to

$$f(m) \sim \sqrt[m]{m!}\ \Gamma(1 + 1/m)\ N^{1-1/m}$$

(for fixed $m$ and asymptotically as $N \to \infty$).