Randomly put $k$ balls in $2n$ circular boxes, pick $n$ consecutive boxes such that the number of balls is minimum!

Question

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.

Answer 1

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

Answer 2

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):
    c=sort(uniform(0,1,k))
    for j in range(1,k):
        for i in range(k):
            if ((c[i] - c[i-j])%(1)> 0.5):
                return(j)
    return(k)
x=[mean([r_unif(k)/k for t in range(100)]) for k in [5,10,15,20,30,50,100,300]]
print(x)

I obtain:

0.34, 0.336, 0.34, 0.351, 0.375, 0.388, 0.417, 0.45