# Probability 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$$ 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 and $$\Delta'=\mathbb{E}\left(1-\min\left(|x-y|,|z-y|\right)~\big|~x,y

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}$$?)

• 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$? – Sam Hopkins Sep 22 '20 at 19:55
• Yes, thank you @SamHopkins – Penelope Benenati Sep 22 '20 at 20:06
• 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}$. – Sam Hopkins Sep 22 '20 at 20:41
• 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}$? – 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.

• 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$. – aorq Sep 23 '20 at 15:36
• @aorq: indeed, I did not try to optimize here. – Sam Hopkins Sep 23 '20 at 16:53
• 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. – Penelope Benenati Sep 26 '20 at 18:56