Skip to main content
1 of 2
Pablo Lessa
  • 4.3k
  • 28
  • 37

As suggested by N. Gast a simpler related problem is to consider uniform independent points on a circle $u_1,u_2,\ldots$ and for each $k$ set $$m_k = \min\limits_{I}|\lbrace u_1,\ldots,u_k\rbrace \cap I|,$$ where the minimum is over all arcs of length one half of the perimeter of the circle.

For this problem the Glivenko-Cantelli theorem implies that $m_k/k \to 1/2$ almost surely when $k \to +\infty$.

So coming back to your original problem if you pick $k = \log(n)$ then one can expect to be able to pick the boxes in which one puts the balls indpendently at random and the probability of picking the same box twice is negligible.

In this situation the random variable you want to understand is more or less $m_k$. So I expect your variable to be of order $k/2$ and the error to be of order $\sqrt{k}$ (following rate estimates in the Glivenko-Cantelli such as Kolmogorov's theorem). So it would be surprising if the expected value wasn't eventually larger than $(1/2-\epsilon)k$ for any $\epsilon > 0$ (even though this doesn't agree with N. Gast's computer experiment).

Pablo Lessa
  • 4.3k
  • 28
  • 37