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

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

• Did you allow $(x, x)$ to be included in $S_p$ on purpose? Those pairs increase the size of $S_p$ without contributing to the sum of distances. – araomis Nov 10 '20 at 21:59
• You can have $(x,y)\in S_p$ such that $x=y$. There are no additional constraints. For instance, If $p=\alpha$ with probability $1$, where $\alpha\in[0,1]$ (i.e., instead of being selected uniformly at random in [0,1] as written in the problem text, $p$ is fixed in $[0,1]$), the problem becomes deterministic and is trivial: one easily obtains $m(n)$ approaching $\max(p,1-p)/2=\max(\alpha,1-\alpha)/2$ as $n$ increases (half of the points placed in $p=\alpha$ and the other half placed in the farthest endpoint from $p=\alpha$ of the interval $[0,1]$). – Penelope Benenati Nov 10 '20 at 22:21
• Thank you @araomis for your answer (previously) below. Why did you delete it? I did not have enough time these days to analyze it, and I would be glad to read it this weekend. – Penelope Benenati Nov 14 '20 at 14:40
• I added it again, sorry. I was not so sure anymore whether it really contributes anything interesting. Let me know ;-). – araomis Nov 15 '20 at 11:22

## 2 Answers

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 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 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 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 For example, a straight forward bound can be obtained by choosing $$\mu$$ itself to be Lebesgue on $$[0,1]$$.

• @Penelope Benenati You are right, I misread. Corrected. – ofer zeitouni Nov 14 '20 at 10:26
• By tight I mean that I expect it to give the correct asymptotics for the maximum (in spite of the fact that it is only a lower bound, which is what you asked about). The reasoning (which I have not tried to transform into a formal proof) goes as follows: suppose you have a near optimal $S=S_n$ (that nearly achieves the maximum). Consider the empirical measure. It has a converging subsequence (as $n\to\infty$) to some measure $\mu$. Now apply the argument I wrote with that $\mu$. – ofer zeitouni Nov 14 '20 at 16:47
• The only places where you need care (in writing a formal proof) is that $1_{x<p<y}$ is not a continuous function of $(x,y)$. But you can get around that by mollification, since $p$ has a smooth law. – ofer zeitouni Nov 14 '20 at 16:49
• Asymptotically, 0 distance. Replace $1_{x<p<y}$ by $g_\epsilon(p,x,y)$ continuous, so that $g_\epsilon(p,x,y)=1$ if $x<p-\epsilon$ and $y>p+\epsilon$ and $g_\epsilon(p,x,y)=0$ if $x> p-\epsilon/2$ and $y>x+\epsilon/2$. Now you get a bound (that depends at $\epsilon$) and then at the end take $\epsilon\to 0$. – ofer zeitouni Nov 14 '20 at 18:25
• What I wrote is that the formula I gave should also be an (asymptotic) upper bound, that is, I believe that $\lim_{n\to\infty} m_n$. equals the formula I wrote. If you want a finite $n$ result then yes, by all means, start another question. I have no idea how to compute a finite $n$ upper bound. – ofer zeitouni Nov 14 '20 at 19:48

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_{: The set $$S_{>p}$$ contains all pairs $$(x, y)$$ with $$\min(x, y) \geq p$$ while $$S_{ 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_{: $$d(S_p) = \frac{1}{\lvert S_p \rvert}\left(\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_{

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}}$$

• Thank you very much for your answer. The approach is clear and looks correct (perhaps there is a typo when you wrote "Thus $S_p$ contains exactly $i^2 + (n - i)^2$ pairs" if I am not wrong, anyway nothing really important). The difficult part is maximizing the last expression over all $s_i$ for $1\le i\le n$. Numerical simulations suggests that we obtain $0.40$ for $n=4$, $0.31$ for $n=8$, less than $0.29$ for $n=16$. Furthermore, the distance between two consecutive points seems to be equal up to $1/(n-1)$ up to a (small) constant factor, and we always have $s_1=0$ and $s_n=1$. – Penelope Benenati Nov 16 '20 at 0:12
• I feel confident that $m(n)$ is monotonically decreasing in $n$. @araomis, do you have any idea related to your expression about how to prove this property? – Penelope Benenati Nov 16 '20 at 13:51
• Thanks for your comments. I have added an edit for the case where the points are distributed equidistantly, but I didn't get so far yet. I'll let you know if I get anywhere (also wrt your conjecture about monotonicity). Considering the line "Thus $S_p$ contains $i^2 + (n - i)^2$ pairs": My idea was that the size of $S_{<p}$ is $i^2$ and the size of $S_{>p}$ is $(n - i)^2$. Together they make up $S_p$. Let me know if you still think there is a mistake, I don't see it yet. – araomis Nov 16 '20 at 17:42
• Thank you for your edit and your comment! About the expression $i^2+(n-i)^2$, you defined $i$ as the the number of points smaller than $p$. You wrote that the set $S_{<p}$ contains all pairs of points smaller than $p$, and its cardinality is equal to $i^2$. If $i=1$, the number such pairs is $0$. If $i=2$ the number of such pairs is $1$. Hence, I am understanding now that (1) when you talk about pairs, you mean ordered pairs, while I was meaning unordered pairs. – Penelope Benenati Nov 16 '20 at 20:26
• Ah, that makes sense. Yes, I misunderstood you, I'll change it. – araomis Nov 17 '20 at 8:04