Balls and Bins Variation (Multiple Rounds)

Question

Consider the following balls and bins experiment: we repeatedly throw a fixed number of balls randomly into a shrinking set of bins. The experiment starts with $n$ balls and $n$ bins. In each round $k,$ we throw $n$ balls into the remaining bins, and then discard any non-empty bins; thus, only bins that are empty at the end of round $k$ survive to round $k + 1$. What is the expected number of rounds before every bin among the initial $n$ is nonempty?

In general, assuming we are conducting the standard balls-and-bins experiment, then given $m$ balls and $n$ bins, we know that the expected number of bins that are empty is $n(1 - \frac{1}{n})^m$. With this in mind, I've attempted to consider each round in the above experiment as an instance of the standard balls into bins problem, and have reformulated the question into an equivalent one, thus:

Suppose that for each round, exactly the expected number of bins are empty. Then after how many rounds does the experiment end?

However, the expected number formula quickly gets unwieldy. But consider the function defined for any integer $i \geq 0$:

$f(i+1) = 2^{f(i)}$ for $i \geq 1$ and $f(0) = 1$

Could I use an induction argument to show that, after round $i$ and before round $i + 1$ (assuming that exactly the expected number of bins are empty for each round), we have that $\frac{n}{f(i+1)} \leq \textit{number of empty bins} < \frac{n}{f(i)}$ and try to tightly bound the solution from above?

Answer 1

Too long for a comment:

A quick (unchecked) attempt suggested to me that for $n=1$ the expected number of rounds to reach $0$ bins remaining is $1$, for $n=2$ is $\frac32$, for $n=3$ is $\frac{65}{36}$ and for $n=4$ is $\frac{845}{432}$, so still fewer than $2$ rounds expected.

I would have thought that $n$ could have to be extremely large for the expected number of rounds to exceed $4$ substantially, possibly slightly related to the iterated logarithm but perhaps closer to base $e$ rather than your suggestion of base $2$.

Suppose there are $n$ balls and $k$ bins. Then the expected number of empty bins after a round is $k\left(1-\frac1k\right)^n$ which for large $n$ and $k$ is about $k\exp(-n/k)$. If $k=n$ this is about $n\exp(-1)$. And then you may need more rounds.

If you have a sequence starting at $a_0=0$ with $a_{m+1} = a_{m}-\exp(-a_m)$ then, for very large $n$, after $m$ rounds you might expect to have about $n\exp(a_m)$ empty bins left. I think the number of remaining bins could be about $n\exp(-1)$ after one round, about $n\exp(-1-\exp(1))$ after two rounds, about $n\exp(-1-\exp(1)-\exp(1+\exp(1)))$ after three, and about $n\exp(-1-\exp(1)-\exp(1+\exp(1)) -\exp(1+\exp(1)+\exp(1+\exp(1))) )$ after four. The first round multiplies $n$ by about $0.368$, the second by about $0.0243$, the third by about $3\times 10^{-20}$ and the fourth multiplies $n$ by a number smaller than $10^{-10000000000000000000}$

Added: As an example, a simulation in R of $10^4$ cases with $n=10^5$ gave a mean of about $36789$ empty bins after $1$ round (standard deviation about $99$), a mean of about $2428$ empty bins after $2$ rounds (standard deviation about $49$), and none after three rounds, so in all $10^4$ cases exactly $3$ rounds required. The actual expected number of rounds required with $n=10^5$ will not be exactly $3$ but it will be extremely close to $3$

Simulation of particular n

set.seed(2020)
cases <- 10^4
n <- 10^5
attempts <- 4
matdat <- matrix(numeric(cases*attempts),ncol=attempts)
for (j in 1:cases){
  remain <- 1:n
  for (i in 1:attempts){
      hit <- remain[sample(length(remain), n, replace=TRUE)]
      remain <- remain[! remain %in% hit]
      matdat[j,i] <- length( remain)
    }
  }
colMeans(matdat)
# 36787.085  2426.781     0.000     0.000
sqrt(colMeans(matdat^2)-colMeans(matdat)^2)
# 99.38073 49.34122  0.00000  0.00000
mean(1 + rowSums(matdat > 0)) # average number of rounds
# 3
mean(matdat[,2] > 0 & matdat[,3] == 0) # proportion finishing 3 rounds
# 1