2
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$ – araomis Nov 10 '20 at 21:59
  • $\begingroup$ 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]$). $\endgroup$ – Penelope Benenati Nov 10 '20 at 22:21
  • 1
    $\begingroup$ 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. $\endgroup$ – Penelope Benenati Nov 14 '20 at 14:40
  • 1
    $\begingroup$ I added it again, sorry. I was not so sure anymore whether it really contributes anything interesting. Let me know ;-). $\endgroup$ – araomis Nov 15 '20 at 11:22
1
+50
$\begingroup$

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

$\endgroup$
10
  • 1
    $\begingroup$ @Penelope Benenati You are right, I misread. Corrected. $\endgroup$ – ofer zeitouni Nov 14 '20 at 10:26
  • 1
    $\begingroup$ 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$. $\endgroup$ – ofer zeitouni Nov 14 '20 at 16:47
  • 2
    $\begingroup$ 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. $\endgroup$ – ofer zeitouni Nov 14 '20 at 16:49
  • 1
    $\begingroup$ 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$. $\endgroup$ – ofer zeitouni Nov 14 '20 at 18:25
  • 1
    $\begingroup$ 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. $\endgroup$ – ofer zeitouni Nov 14 '20 at 19:48
1
$\begingroup$

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

$\endgroup$
6
  • 1
    $\begingroup$ 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$. $\endgroup$ – Penelope Benenati Nov 16 '20 at 0:12
  • $\begingroup$ 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? $\endgroup$ – Penelope Benenati Nov 16 '20 at 13:51
  • 1
    $\begingroup$ 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. $\endgroup$ – araomis Nov 16 '20 at 17:42
  • $\begingroup$ 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. $\endgroup$ – Penelope Benenati Nov 16 '20 at 20:26
  • 1
    $\begingroup$ Ah, that makes sense. Yes, I misunderstood you, I'll change it. $\endgroup$ – araomis Nov 17 '20 at 8:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.