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$ Sep 27, 2020 at 0:17
  • 1
    $\begingroup$ Also, can you show the derivation of $\rho=\frac{16}{17}$ for $\mathcal{D}$ uniform? $\endgroup$ Sep 27, 2020 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$ Sep 27, 2020 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$ Sep 27, 2020 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$ Sep 27, 2020 at 14:52

1 Answer 1

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$ Oct 1, 2020 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, 2020 at 3:14
  • $\begingroup$ Thank you @Matt $\endgroup$ Oct 5, 2020 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.