1
$\begingroup$

Let $X$ be a finite set and $\sigma_0$, $\sigma_1$ two fixed measures on $X$ with $\sigma_0(X)=\sigma_1(X)$. A transportation plan is a measure $\mu$ on $X\times X$ whose projections on the first and second factor $X$ are $\sigma_0$ and $\sigma_1$ respectively. For a metric $\rho$ on $X$, the optimal cost $\rm{opt(}\rho\rm{)}$ is the minimum of $\int \rho \rm{d}\mu$ over all plans $\mu$ (for the fixed $\sigma_0$ and $\sigma_1$).

Take two metrics $\rho$ and $\rho'$ on $X$. Question: Is there an upper bound for $\rm{opt(}\rho+\rho'\rm{)}$ in terms of $\rm{opt(}\rho\rm{)}$ and $\rm{opt(}\rho'\rm{)}$? In particular, is $\rm{opt(}\rho+\rho'\rm{)}$ small whenever $\rm{opt(}\rho\rm{)}$ and $\rm{opt(}\rho'\rm{)}$ are small?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
1
$\begingroup$

$\newcommand\opt{\operatorname{opt}}\newcommand\de{\delta}\newcommand\si{\sigma}$The answer is no.

Indeed, take any $h\in(0,1)$. Let $X=\{1,2,3,4\}$. Suppose that $$\si_0=\frac12\de_1+\frac12\de_4,\quad\si_1=\frac12\de_2+\frac12\de_3$$ (where $\de_a$ is the Dirac probability measure supported on $\{a\}$), $$\rho(1,2)=\rho(3,4)=h,\quad\rho(1,3)=\rho(1,4)=\rho(2,3)=\rho(2,4)=1,$$ $$\rho'(1,3)=\rho'(2,4)=h,\quad\rho'(1,2)=\rho'(1,4)=\rho'(2,3)=\rho'(3,4)=1$$ (such metrics $\rho$ and $\rho'$ clearly exist).

Then

  • $\opt(\rho)\le h$ (witnessed by $\mu=\frac12\de_{(1,2)}+\frac12\de_{(4,3)}$)
  • $\opt(\rho')\le h$ (witnessed by $\mu'=\frac12\de_{(1,3)}+\frac12\de_{(4,2)}$).

On the other hand, $(\rho+\rho')(i,j)\ge1+h$ for distinct $i$ and $j$ in $X$, whereas the support sets of $\si_0$ and $\si_1$ are disjoint. Therefore, $\opt(\rho+\rho')\ge1+h$, so that $$\frac{\opt(\rho+\rho')}{\opt(\rho)+\opt(\rho')}\ge\frac{1+h}{2h}\to\infty$$ as $h\downarrow0$.

Improve this answer
$\endgroup$
6
  • $\begingroup$ That is a good point but I don't think it answers the question. The question is about the possibily of such an estimate when you fix the metrics (i think). Here you are constructing a family of metrics for which the condition is violated, but this does not prevent the possibility that for any $\rho, \rho^\prime$ there exists a constant $C(\rho, \rho^\prime)$ such that $opt(\rho + \rho^\prime) \leq C(\rho, \rho^\prime)( opt(\rho) + opt(\rho^\prime))$ $\endgroup$
    – Castoro Moro
    Commented Oct 11 at 13:36
  • $\begingroup$ @CastoroMoro : The problem according to your understanding would be trivial. Indeed, in the nontrivial case $\sigma_0\ne\sigma_1$ we will have $\operatorname{opt}(\rho)>0$ and $\operatorname{opt}(\rho')>0$, so that we will have $\operatorname{opt}(\rho+\rho')=C(\operatorname{opt}(\rho)+\operatorname{opt}(\rho'))$ with $C:=\operatorname{opt}(\rho+\rho')/(\operatorname{opt}(\rho)+\operatorname{opt}(\rho'))$. $\endgroup$
    – Iosif Pinelis
    Commented Oct 11 at 13:44
  • $\begingroup$ But your constant depends on the probability measures $\sigma_0, \sigma_1$, if I am not mistaken. In my formulation the constant $C(\rho, \rho^\prime)$ depends only on the metrics. $\endgroup$
    – Castoro Moro
    Commented Oct 11 at 13:47
  • 1
    $\begingroup$ @CastoroMoro : The OP says "$\sigma_0$, $\sigma_1$ two fixed measures". $\endgroup$
    – Iosif Pinelis
    Commented Oct 11 at 13:50
  • 1
    $\begingroup$ In case this is not clear from the way the question is written: What I was looking for is solved by Iosif Pinelis's answer. There may be other related questions, along the lines of Castoro Moro's comment, but my question was answered. $\endgroup$
    – user95282
    Commented Oct 11 at 15:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .