Let $\mathcal{D}$ be a probability distribution with support $[0,1]$. Let $X, Y, Z$ three i.i.d. random variables with distribution $\mathcal{D}$, and $T$ a random variable uniformly distributed in $[0,1]$ independent from $X$, $Y$ and $Z$. We define $$\Delta=\mathbb{E}\left(1-|x-y|~\big|~x,y<t<z\right)$$ and $$\Delta'=\mathbb{E}\left(1-\min\left(|x-y|,|z-y|\right)~\big|~x,y<t<z\right)~.$$

Question: What is the minimum value of the ratio $\rho=\frac{\Delta}{\Delta'}$ over all probability distributions $\mathcal{D}$? (If $\mathcal{D}$ is uniform, then $\rho=\frac{16}{17}$. Is there a distribution $\mathcal{D}$ such that $\rho<\frac{16}{17}$?)

  • 1
    $\begingroup$ Are $X,Y,Z$ independent (it seems like you're assuming that but you don't say explicitly)? Similarly, $T$ independent from $X,Y,Z$? $\endgroup$ – Sam Hopkins Sep 22 '20 at 19:55
  • $\begingroup$ Yes, thank you @SamHopkins $\endgroup$ – Penelope Benenati Sep 22 '20 at 20:06
  • 1
    $\begingroup$ Random check: if $\mathcal{D}$ is supported on $\{0,3/4,1\}$ and takes values $0$ and $3/4$ equally often, then I think I calculated $\rho=\frac{32}{33}$. $\endgroup$ – Sam Hopkins Sep 22 '20 at 20:41
  • $\begingroup$ Thank you @SamHopkins In this case, the result that I calculated seems to depend on how often $0$ and $3/4$ are taken. I think there is misunderstanding that I would like to clarify. There are are only $5$ cases satisfying the condition $x,y<t<z$, which I represent with triplets of variables taken values in the support $\{0,3/4,1\}$: $\{x,y,z\}$, $\{y,x,z\}$, $\{(x,y), z, \cdot\}$, $\{(x,y),\cdot, z\}$, $\{\cdot,(x,y), z\}$, right? How did you calculate $\rho=\frac{32}{33}$? $\endgroup$ – Penelope Benenati Sep 23 '20 at 13:24

Sorry, my computation in the comments was wrong. I think it leads to something with $\rho < \frac{16}{17}$.

Namely, let $\mathcal{D}$ be the distribution with $\mathrm{Pr}(\mathcal{D}=0)=\mathrm{Pr}(\mathcal{D}=3/4)=1/N$, and $\mathrm{Pr}(\mathcal{D}=1)=(N-2)/N$, where $N$ is large.

Then the possibilities for $(x,y,z)$ which fit your conditional probability are:

  • $0 < t < \frac{3}{4}$: $(0,0,\frac{3}{4})$, $(0,0,1)$
  • $\frac{3}{4} < t < 1$: $(0,0,1)$, $(0,0,1)$, $(0,\frac{3}{4},1)$, $(\frac{3}{4},0,1)$, $(\frac{3}{4},\frac{3}{4},1)$

Only one of these has $z\neq 1$; if $N$ is very large, then that case will occur much less frequently and we can "ignore" it (so we're really doing the limit $N\to \infty$ computation, for convenience).

Let $\delta=1-|x-y|$ and $\delta'=1-\min(|x-y|,|z-y|)$. Then the events to consider, and their probabilities and values, are

  • $0 < t < \frac{3}{4}$: $(0,0,1)$ - relative prob. $\frac{3}{7}$, $\delta=\delta'=1$
  • $\frac{3}{4} < t < 1$: $(0,0,1)$ - relative prob. $\frac{1}{7}$, $\delta=\delta'=1$
  • $\frac{3}{4} < t < 1$: $(0,\frac{3}{4},1)$ - relative prob. $\frac{1}{7}$, $\delta=\frac{1}{4}$, $\delta'=\frac{3}{4}$
  • $\frac{3}{4} < t < 1$: $(\frac{3}{4},0,1)$ - relative prob. $\frac{1}{7}$, $\delta=\delta'=\frac{1}{4}$
  • $\frac{3}{4} < t < 1$: $(\frac{3}{4},\frac{3}{4},1)$ - relative prob. $\frac{1}{7}$, $\delta=\delta'=1$

So we can compute $$\Delta=\frac{3}{7}+\frac{1}{7}+\frac{1}{7}(\frac{1}{4})+\frac{1}{7}(\frac{1}{4})+\frac{1}{7}=\frac{11}{14}$$ $$\Delta'=\frac{3}{7}+\frac{1}{7}+\frac{1}{7}(\frac{3}{4})+\frac{1}{7}(\frac{1}{4})+\frac{1}{7}=\frac{12}{14}$$ $$\rho=\frac{\Delta}{\Delta'}=\frac{11}{12}< \frac{16}{17}$$

As mentioned, really we took the limit $N\to \infty$; but since we got $\rho< \frac{16}{17}$, that means there should be some finite $N$ we can take with $\rho< \frac{16}{17}$, just the computation will be more annoying.

  • 2
    $\begingroup$ Suppose $m=3/4$ is allowed to vary as well. Then my calculations suggest that $\rho=1-3/35 < 11/12 = 1-3/36$ when $m=4/5$, and that the minimum over all $m$ is $\sqrt{2}-1/2$ at $m=3/2-1/\sqrt{3}$. I think one can get below $8/9$ if you also vary the relative probability of $0$ and $m$. $\endgroup$ – aorq Sep 23 '20 at 15:36
  • 1
    $\begingroup$ @aorq: indeed, I did not try to optimize here. $\endgroup$ – Sam Hopkins Sep 23 '20 at 16:53
  • $\begingroup$ Thank you very much @SamHopkins and aorq ! This problem originated from its "symmetric" version that I just posted here: mathoverflow.net/q/372688/115803. Initially, I posted this problem thinking I could easily extend any answer to its "symmetric" (original) version. However, it seems that it is not possible, and I think that the minimum $\frac{16}{17}$ is attained by the uniform distribution $\mathcal{D}$ in the symmetric version. Do you have any idea about whether it is possible to extend this result to the symmetric (original) problem? Thanks. $\endgroup$ – Penelope Benenati Sep 26 '20 at 18:56

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.