**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
```