Let $S$ be a set of $n \gg 1$ points lying on the interval $[0,1]$. Given a point $p\in[0,1]$, let $S\_p\subseteq S\times S$ be the set formed by all pairs of points $(x,y)$ with $x,y\in S$, such that either $\max(x,y)\le p$ or $\min(x,y)\ge p$. Finally let $d(S\_p)=\frac{1}{|S\_p|}\sum\_{(x,y)\in S\_p} |x-y|$ be the average distance between any two points in $S\_p$.




---


**Question:** If $p$ is selected uniformly at random in $[0,1]$, what is the maximum expected value
$m(n)$ of $d(S\_p)$ over all possible sets $S$ of $n$ points in $[0,1]$ (i.e., $m(n):=\max\_{S\in[0,1]^n}\mathbb{E}\_p\left[d(S\_p)\right]$)?




---




---


*Can we at least find a good lower bound for $m(n)$, when $n\to\infty$?*


*Can we calculate the value of $m(n)$ if $p$ is equal to $\tfrac14$, $\tfrac12$ and $\tfrac34$, all with probability $\tfrac13$ (instead of being selected uniformly at random in $[0,1]$)? (I guess it's a simpler question and can provide insights about the main problem above.)*



Probabilistic combinatorial optimization problem on the distances between pairs of points in $[0,1]$
Here is an approach that gives a lower bound, that I expect to be tight.
The first step is to observe that if $\mu$ is a non-atomic
probability distribution on $[0,1]$,
$(X\_i)\_{i=1}^n$ are iid and $\mu$ distributed, and $L\_n=n^{-1} \sum\_{i=1}^n \delta\_{X\_i}$ the associated empirical measure, then
$$ m\_n\geq E\_\mu\times E\_p \big( \frac{\int\int L\_n(dx) L\_n(dy) (1-1\_{x< p< y})|x-y|}{\int \int L\_n(dx) L\_n(dy) (1-1\_{x<p<y})}\big).$$
Now, $$\int\int L\_n(dx) L\_n(dy) (1-1\_{x< p< y})|x-y|\to\_{n\to\infty}\int\int \mu(dx)\mu(dy)|x-y|(1-1\_{x<p<y})$$
and
$$\int\int L\_n(dx) L\_n(dy) (1-1\_{x< p< y})\to\_{n\to\infty}\int\int \mu(dx)\mu(dy)(1-1\_{x<p<y})$$
So altogether,
asymptotically,
$$ \liminf\_{n\to\infty}m\_n \geq \sup\_{\mu}\int\_0^1 dp \frac {\int\int \mu(dx)\mu(dy)|x-y|(1-1\_{x<p<y})}{\int\int \mu(dx)\mu(dy)(1-1\_{x<p<y})}.$$
For example, a straight forward bound can be obtained by choosing $\mu$ itself to be Lebesgue on $[0,1]$.


