3
$\begingroup$

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

$\endgroup$
13
  • 2
    $\begingroup$ 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]$? $\endgroup$ – Sam Hopkins Sep 27 '20 at 0:17
  • 1
    $\begingroup$ Also, can you show the derivation of $\rho=\frac{16}{17}$ for $\mathcal{D}$ uniform? $\endgroup$ – Sam Hopkins Sep 27 '20 at 1:32
  • 1
    $\begingroup$ 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. $\endgroup$ – Sam Hopkins Sep 27 '20 at 13:27
  • 1
    $\begingroup$ 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|)$. $\endgroup$ – Sam Hopkins Sep 27 '20 at 14:45
  • 1
    $\begingroup$ 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$. $\endgroup$ – Sam Hopkins Sep 27 '20 at 14:52
3
+50
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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))]~.$$ $\endgroup$ – Penelope Benenati Oct 1 '20 at 14:29
  • 1
    $\begingroup$ 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. $\endgroup$ – Matt F. Oct 5 '20 at 3:14
  • $\begingroup$ Thank you @Matt $\endgroup$ – Penelope Benenati Oct 5 '20 at 14:35

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.