Return to 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 $\tfrac13$ and $\tfrac23$ with probability $\tfrac12$ (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)

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

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 tight lower bound for $m(n)$, when $n\to\infty$?

Can we calculate the value of $m(n)$ if $p$ is equal to $\tfrac13$ and $\tfrac23$ with probability $\tfrac12$ (instead of being selected uniformly at random in $[0,1]$)? (I guess it's simpler and can provide insights about the main 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 $\tfrac13$ and $\tfrac23$ with probability $\tfrac12$ (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)

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 tight lower bound for $m(n)$, when $n\to\infty$?

Can we calculate the value of $m(n)$ if $p$ is equal to $\tfrac13$ and $\tfrac23$ with probability $\tfrac12$ (instead of being selected uniformly at random 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 tight lower bound for $m(n)$, when $n\to\infty$?

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