Suppose there are $m$ balls and $n$ bins where $m \geq n$. The $m$ balls are thrown into the $n$ bins uniformly at random. At the end of each round, all bins with less than the maximum number of balls is removed. Let the remaining number of bins be $n_1$. The process is repeated with $m$ balls and $n_1$ bins, and so on. The question is, what is the expected number of rounds necessary until one bin remains?

One can get a weak bound of $\lg n$ rounds by using the well-known result for expected number of empty bins: $n/e$. But I'm hoping for a tighter bound.

Has anyone ever seen this question before perhaps named differently? Intuitively, this is the opposite of what we want with balls and bins (because that's used most often in load balancing), but I don't know a better name to ask this question under.

  • $\begingroup$ Just to make sure I understand correctly, if $n|m$, and every bin winds up with the same number of balls, do you keep all $n$ bins to the next round? $\endgroup$ Jun 18, 2019 at 20:17
  • $\begingroup$ Yes, if all bins end up with the same number of balls, you keep all the bins. $\endgroup$ Jun 18, 2019 at 20:18


You must log in to answer this question.

Browse other questions tagged .