Return to Answer

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 = S \times S$. 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 $2i(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{2}{\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 $i^2 + (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{2}{\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{2}{i^2 + (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{2}{i^2 + (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{2}{(n-1)^2}\sum_{i = 1}^n \frac{1}{i^2 + (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{2}{(n-1)^2}\sum_{i = 1}^n \frac{1}{i^2 + (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{2}{(n-1)^2}\sum_{i = 1}^n \frac{1}{i^2 + (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}{3(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)}{i^2 + (n -i)^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}} $$

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 = S \times S$. 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 $2i(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{2}{\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 $i^2 + (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{2}{\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{2}{i^2 + (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) $$

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 = S \times S$. 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 $2i(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{2}{\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 $i^2 + (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{2}{\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{2}{i^2 + (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{2}{i^2 + (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{2}{(n-1)^2}\sum_{i = 1}^n \frac{1}{i^2 + (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{2}{(n-1)^2}\sum_{i = 1}^n \frac{1}{i^2 + (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{2}{(n-1)^2}\sum_{i = 1}^n \frac{1}{i^2 + (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}{3(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)}{i^2 + (n -i)^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 particular 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 = S \times S$. 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 $2i(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{2}{\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 $i^2 + (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{2}{\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) \\ = 2\sum_{i = 0}^n (s_{i + 1} - s_i) \frac{1}{i^2 + (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) $$

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 = S \times S$. 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 $2i(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{2}{\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 $i^2 + (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{2}{\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{2}{i^2 + (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) $$