You are given $2n$ boxes that are arranged circular (you can imagine all boxes are on the edge of a circular table). Then randomly, you put $k$ balls in the boxes such that each box is containing either 0 or 1 ball.

What you have to do is to pick $n$ consecutive boxes such that the number of balls you pick is as small as possible. What is the expected number of this number (the number of balls)?

On a special case, what if $k \approx\log n$?

Reference/Motivation. This is actually one of my work to attack this question: Painting $n$ balls from $2n$ balls red, and guessing which ball is red, game.


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

| cite | improve this answer | |
  • $\begingroup$ I would expect the birthday paradox to work in our favor here. If we consider an alternative model where we allow multiple balls to land in the same bin, the extra clumping should only reduce the number of balls in the sparsest interval. $\endgroup$ – Kevin P. Costello Jul 29 '16 at 21:54

edit At first, my simulation suggested that the exact value was $k/3$ but I am now convinced that it is $k/2$. Yet, the convergence speed to $k/2$ seems smaller than $1/\sqrt{k}$.

When $n$ is large with respect to $k$, it seems that you can replace your problem by picking $k$ random variables $U_{i}$ uniform between 0 and 1. Then you want to find an interval that contains as few balls as possible. This can be easily simulated.

You can also use this approach to show that your asymptotically, your expectation is between $k/2-\epsilon$ and $k/2$. The $k/2$ bound is obvious. For $k/4$, you know that the chosen interval will contains of the the fourth intervals [0,1/4], [1/4,1/2], [1/2,3/4] and [3/4,1]. Asymptotically, each interval will contain $k/4$ balls. Then, as Douglas pointed out, you can use more intervals to obtain $k/2-\epsilon$.

Here is the python program that I used to simulate your problem:

from numpy import sort,mean
from numpy.random import uniformdef r_unif(k):
    for j in range(1,k):
        for i in range(k):
            if ((c[i] - c[i-j])%(1)> 0.5):
x=[mean([r_unif(k)/k for t in range(100)]) for k in [5,10,15,20,30,50,100,300]]

I obtain:

0.34, 0.336, 0.34, 0.351, 0.375, 0.388, 0.417, 0.45
| cite | improve this answer | |
  • $\begingroup$ I actually haven't tried to simulate it because for a small number $k$, the answer "may be" converge to $k/f(n,k)$ for some function $f$. And if such $f$ is small relative to $n$ and/or $k$ (take an example $f = \log k$), $f$ can't be distinguished with a constant (I suppose). Before that, could you elaborate more for lowerbound $k/4$? Why can't it be $k/c$ for $c>4$ with the same reason? $\endgroup$ – user95536 Jul 29 '16 at 14:06
  • 2
    $\begingroup$ I don't believe the $k/3$ result. The argument you give for the $k/4$ lower bound can be modified very simply to give $(1/2-\epsilon)k$ by using more sectors, e.g., with $10$ equal $\pi/5$ sectors any semicircle contains at least $4$ so for large $k$, the minimum is at least $0.4k$. $\endgroup$ – Douglas Zare Jul 29 '16 at 21:48
  • $\begingroup$ Douglas: I agree with your reasoning. The problem with my simulations was that at first, I only simulated up to $n=10^6$ (which is $k=14$), for which the value seems to concentrate around 0.33. For $n=1000$, it is closer to $k/2$. $\endgroup$ – N. Gast Jul 30 '16 at 7:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy