Probabilistic combinatorial optimization problem on the distances between pairs of points in $[0,1]$

Question

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

Answer 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]$.

Answer 2

I was not able to answer any of your questions yet. However, I have derived a close form solution for the expectation $\mathbb{E}_p(d(S_p))$, given a set $S$. If my derivation is correct, it seems to me that we might be able to compute $\max_{S \in [0, 1]} \mathbb{E}_p(d(S_p))$ using mathematical optimization techniques on the closed form solution.

Let $S \subset \mathbb{R}$ be a finite set of $n$ points and consider $S^2 = \binom{S}{2}$. We first study $d(S^2) = \frac{1}{\lvert S^2 \rvert}\sum_{(x, y) \in S^2} \lvert x - y \rvert$. To this end, consider the points of $S$ sorted from least to largest: $s_1, \dots, s_n$. For arbitrary $i \in [n-1]$ we observe that there are exactly $i(n - i)$ pairs $(x, y) \in S^2$ such that the line segment $\overline{s_i s_{i + 1}}$ is contained in the line segment $\overline{xy}$. We get: $$d(S^2) = \frac{1}{\lvert S^2 \rvert}\sum_{i = 1}^{n - 1}i(n - i)(s_{i + 1} - s_i)$$

Next, let $p \in [0, 1]$ such that $p \notin S$. Consider the set $S_p$ as you defined it. The point $p$ splits the points in $S$ into two parts: Those larger than $p$ and those smaller than $p$. Assume that exactly $i$ points are smaller than $p$. The set $S_p$ consists of two disjoint subsets $S_{>p}$ and $S_{<p}$: The set $S_{>p}$ contains all pairs $(x, y)$ with $\min(x, y) \geq p$ while $S_{<p}$ is the set of all pairs $(x, y)$ with $\max(x, y) \leq p$. Thus $S_p$ contains exactly $\binom{i}{2} + \binom{n - i}{2}$ pairs. Moreover, we can use the formula from above on $S_{>p}$ and $S_{<p}$: $$d(S_p) = \frac{1}{\lvert S_p \rvert}\left(\sum_{(x, y) \in S_{<p}} \lvert x - y \rvert + \sum_{(x, y) \in S_{>p}} \lvert x - y \rvert\right) \\ = \frac{1}{\lvert S_p \rvert}\left( \lvert S_{>p} \rvert d(S_{>p}) + \lvert S_{<p} \rvert d(S_{<p}) \right)\\ = \frac{1}{\lvert S_p \rvert}\left( \sum_{j = 1}^{i - 1}j(i - j)(s_{j + 1} - s_j) + \sum_{j = i}^{n - 1}(j - i + 1)(n - (j + 1))(s_{j + 1} - s_j)\right)$$

Hence we have a closed form formula for $d(S_p)$ for some particular $S$ and $p \notin S$. As a next step we notice that the probability that exactly $i$ points of $S$ are smaller than $p$ is equal to the probability of $p$ lying on the segment $\overline{s_i s_{i + 1}}$ which of course is equal to the length of the segment $\overline{s_i s_{i + 1}}$. Hence we have derived a closed form for the expectation $\mathbb{E}_p(d(S_p))$ for given $S$. For simplicity, define $s_0 = 0$ and $s_{n + 1} = 1$:

$$\mathbb{E}_p(d(S_p)) = \sum_{i = 0}^n Pr(p \in \overline{s_i s_{i + 1}}) d(S_p) \\ = \sum_{i = 0}^n (s_{i + 1} - s_i) \frac{1}{\binom{i}{2} + \binom{n - i}{2}}\left( \sum_{j = 1}^{i - 1}j(i - j)(s_{j + 1} - s_j) + \sum_{j = i}^{n - 1}(j - i + 1)(n - (j + 1))(s_{j + 1} - s_j)\right) $$

EDIT: If the points are spread equidistantly the formula simplifies to: $$\sum_{i = 0}^n (s_{i + 1} - s_i) \frac{1}{\binom{i}{2} + \binom{n - i}{2}}\left( \sum_{j = 1}^{i - 1}j(i - j)(s_{j + 1} - s_j) + \sum_{j = i}^{n - 1}(j - i + 1)(n - (j + 1))(s_{j + 1} - s_j)\right) \\ = \frac{1}{(n-1)^2}\sum_{i = 1}^n \frac{1}{\binom{i}{2} + \binom{n - i}{2}} \left( \sum_{j = 1}^{i - 1}j(i - j) + \sum_{j = i}^{n - 1}(j - i + 1)(n - (j + 1)) \right) \\ = \frac{1}{(n-1)^2}\sum_{i = 1}^n \frac{1}{\binom{i}{2} + \binom{n - i}{2}} \left( \sum_{j = 1}^{i - 1}j(i - j) + \sum_{j = 1}^{n - i}j(n - i + 1 - j) \right) $$

There is a formula for the two inner sums: $\sum_{j = 1}^{i - 1}j(i - j) = i\sum_{j = 1}^{i - 1}j - \sum_{j = 1}^{i - 1}j^2 = i\frac{i(i - 1)}{2} + \frac{(i - 1)i(2(i - 1) + 1)}{6} = \frac{3i^2(i - 1) + 2(i - 1)^2i + i(i - 1)}{6} = \frac{3i^3 - 3i^2 + 2i^3 - 4i^2 + 2i + i^2 - i}{6} = \frac{5i^3 - 6i^2+ i}{6}$

Plugging this in yields: $$\frac{1}{(n-1)^2}\sum_{i = 1}^n \frac{1}{\binom{i}{2} + \binom{n - i}{2}} \left( \frac{5i^3 - 6i^2+ i}{6} + \frac{5(n - i + 1)^3 - 6(n - i + 1)^2+ (n - i + 1)}{6} \right) \\ = \frac{1}{6(n-1)^2}\sum_{i = 1}^n \frac{5i^3 - 6i^2+ i + 5(n - i + 1)^3 - 6(n - i + 1)^2+ (n - i + 1)}{\binom{i}{2} + \binom{n - i}{2}} $$