Skip to main content
MathOverflow

Return to Answer

mentioned birthday paradox, added links to theorems
Source Link
Pablo Lessa
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 theoremGlivenko-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 (here we should look out for the birthday paradox, I think $\log(n)$ is safe but anything larger than $\sqrt{n}$ could lead to trouble).

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 theoremKolmogorov'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).

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).

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 (here we should look out for the birthday paradox, I think $\log(n)$ is safe but anything larger than $\sqrt{n}$ could lead to trouble).

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).

Source Link
Pablo Lessa
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).