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](https://mathoverflow.net/questions/185074/painting-n-balls-from-2n-balls-red-and-guessing-which-ball-is-red-game).



Randomly put $k$ balls in $2n$ circular boxes, pick $n$ consecutive boxes such that the number of balls is minimum!
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](https://en.wikipedia.org/wiki/Glivenko%E2%80%93Cantelli_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](https://en.wikipedia.org/wiki/Birthday_problem), 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](https://en.wikipedia.org/wiki/Kolmogorov%E2%80%93Smirnov_test)). 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).


