# Symmetric distribution optimization problem of distances between points in $[0,1]$

Let $$\mathcal{D}$$ be a probability distribution with support $$[0,1]$$. Let $$x, y, z$$ the outcomes of three i.i.d. random variables $$X, Y, Z$$ with distribution $$\mathcal{D}$$, sorted in increasing order, i.e., $$x\le y\le z$$, . Let $$a=y-x$$ and $$b=z-y$$. We define

$$\Delta=1-\mathbb{E}\left[\frac{b}{a+b}\cdot a+\frac{a}{a+b}\cdot b\right]=1-\mathbb{E}\left[\frac{2ab}{a+b}\right]$$

and

$$\Delta'=1-\mathbb{E}\left[\min(a,b)\right]~.$$

Question: What is the minimum value of the ratio $$\rho(\mathcal{D})=\frac{\Delta}{\Delta'}$$ over all probability distributions $$\mathcal{D}$$? (When $$\mathcal{D}$$ is uniform in $$[0,1]$$, we have $$\rho=\frac{20}{21}$$. Is there a distribution $$\mathcal{D}^*$$ such that $$\rho(\mathcal{D}^*)< \frac{20}{21}$$?)

Note: This problem can be viewed as the "symmetric version" of question Probability distribution optimization problem of distances between points in the interval $[0,1]$ and is related to the (discrete) combinatorial problem Combinatorial optimization on the sums of differences of real numbers

• Are you sure this is stated correctly? As stated $\Delta$ looks close to $2$ but $\Delta'$ close to $1$. Maybe you mean $\Delta = \mathbb{E}[\begin{cases} 1-|x-y| &\textrm{if$x,y<t<z$} \\ 1-|y-z| &\textrm{if$x<t<y,z$}\end{cases}| x,y<t < z \textrm{ or } x<t<y,z]$? – Sam Hopkins Sep 27 '20 at 0:17
• Also, can you show the derivation of $\rho=\frac{16}{17}$ for $\mathcal{D}$ uniform? – Sam Hopkins Sep 27 '20 at 1:32
• Huh, numerical simulations are not agreeing with the value $16/17$, and something seems a little fishy in your integrals in that you've dropped the absolute value signs. – Sam Hopkins Sep 27 '20 at 13:27
• The problem with your previous evaluation was you were trying to treat $x$ and $y$ as symmetric in the case $x,y < t < z$, but they are not symmetric for the value $1-\min(|x-y|,|z-y|)$. – Sam Hopkins Sep 27 '20 at 14:45
• With the new formulation, my computer is telling me that if $\mathcal{D}$ is the (discrete) uniform distribution on $\{0, 1/3, 2/3, 1\}$, then we get $\Delta/\Delta'=9/10$. – Sam Hopkins Sep 27 '20 at 14:52

If $$\mathcal{D}$$ has density of $$16/13$$ on $$[0,13/32]\cup[19/32,1]$$, with no support elsewhere, then $$\Delta=0.840$$, $$\Delta'=0.887$$, and the ratio is $$0.947$$. This is less than the $$20/21 = 0.952$$ from the uniform distribution.
This may not be close to minimal overall, but it's close to minimal for distributions supported uniformly on $$[0,u]\cup[1-u,1]$$.
• Thank you a lot @Matt Do you think one can find a similar argument even when $\Delta$ and $\Delta'$ are defined as follows (note that, in this case, we indeed have $\rho=16/17$ if $\mathcal{D}$ is uniform in $[0,1]$)? $$\Delta=\mathbb{E}[a(1-b)+b(1-a)]$$ and $$\Delta'=\mathbb{E}[(a+b)(1-\min(a,b))]~.$$ – Penelope Benenati Oct 1 '20 at 14:29
• For that definition, the uniform density on $[0,1/3]\cup [2/3,1]$ gets $\Delta=29/60$, $\Delta'=83/160$, and a ratio of $0.932$. This is less than the $16/17=0.941$ for the uniform distribution on $[0,1]$. However, I won't make further comments on variants of these problems. – Matt F. Oct 5 '20 at 3:14