2

The following is a question from a previous assignment that I was unable to complete. Any assistance on how to complete this would be appreciated.

Let $\varrho: X\times X\to \Bbb R^+$ be a metric on $X$ and let $\phi: \Bbb R^+ \to \Bbb R^+$ be a function such that

  1. $\phi(0)=0$

  2. $\phi$ is strictly increasing, i.e. for $x_1<x_2$ we have $\phi(x_1)<\phi(x_2)$

  3. $\phi$ is concave, i.e. for $0\le\alpha\le 1$ and $x_1<x_2$ $$ \phi(\alpha x_1+(1-\alpha)x_2)\ge\alpha \phi(x_1)+(1-\alpha)\phi(x_2). $$

Then $\phi\circ\varrho$ is a metric. [Hint: show that $\phi$ is sub-additive, that is $$ \phi(a+b)\le\phi(a)+\phi(b) $$ for $a,b\ge0$].

Keeley Hoek
  • 2,929
Zac
  • 133
  • 1
    Once you prove that $\phi$ is subadditive, everything is obvious. Isn't it? – Crostul Apr 19 '15 at 10:25
  • I didn't think so to begin with, but now after running through the question again I would agree with you. – Zac Apr 20 '15 at 15:18

2 Answers2

2

Of all the properties of a distance, the one requiring some work is the triangle inequality. Before tackling it, note the following: in (3) take $\alpha = \frac 1 2, x_2=0, x_1=x$. Then $\phi (\frac 1 2 x) \geq \frac 1 2 \phi (x)$ (using also (1)).

Since $\phi$ is increasing and $\rho$ satisfies the triangle inequality , $\phi \circ \rho (x,y) = \phi (\rho (x,y)) \leq \phi (\rho(x,z) + \rho(z,y)) \leq 2 \phi (\frac 1 2 \rho(x,z) + \frac 1 2 \rho(z,y)) \leq 2(\frac 1 2 \phi (\rho(x,z)) + \frac 1 2 \phi(\rho(z,y))) = \phi (\rho (x,z)) + \phi (\rho(z,y)) = \phi \circ \rho (x,z) + \phi \circ \rho (z,y).$

Note that in the chain above, the 2nd "$\leq$" sign comes from what we have shown in the 1st paragraph.

EDIT: As shown in the comments below, this "proof" contains a mistake (it has been used that $\phi$ is convex, when in fact it is concave). For the correct proof see @Zac's comment below.

Alex M.
  • 35,207
  • Non-strict increasing might allow $\phi(x)\equiv 0$ – Hagen von Eitzen Apr 19 '15 at 10:33
  • @HagenvonEitzen: Thank you, removed that. – Alex M. Apr 19 '15 at 10:35
  • But you were right: If one adds that $\phi(x)=0\to x=0$ or simply that $\phi$ is not identically zero, then strictly increasing is not needed (by concavity, $f(x_1)=f(x_2)$ with $x_2>x_1$ implies that $f$ is constant at least on $[x_1,\infty)$ – Hagen von Eitzen Apr 19 '15 at 10:38
  • 2
    @AlexM: It looks like your 3rd "$\le$ uses sub-additivity. Can we simply use sub-additivity to go from your third step to your sixth step, that is $\phi (\rho(x,z) + \rho(z,y))$ to $\phi (\rho (x,z)) + \phi (\rho(z,y))$? – Zac Apr 20 '15 at 15:19
  • @Zac: No, it is not sub-additivity, because the $\frac 1 2$ gets out of $\phi$, which sub-additivity alone does not guarantee. The truth is that this third "$\leq$" sign contains a mistake: I was under the impression that the function was convex instead of concave. The proof is wrong. Please "un-accept" it in order for me to delete it. – Alex M. Apr 20 '15 at 18:41
  • 2
    @AlexM. I still believe your answer is correct. I've shown that there is sub-additivity as follows:

    From (3), let $x_2=0$, and we get $\phi(\alpha x_1+(1-\alpha) x_2 )\ge\alpha\phi(x_1)+(1-\alpha)\phi(x_2)\Rightarrow\phi(\alpha x_1)\ge\alpha\phi(x_1)$. Now we have $\phi(a)+\phi(b)=\phi(a\frac{a+b}{a+b})+\phi(b\frac{a+b}{a+b})\ge\frac{a}{a+b} \phi(a+b)+\frac{b}{a+b}\phi (a+b)=\phi(a+b)$. Thus $\phi$ is sub-additive. From this, you can say that $\phi(\rho(x,z)+\rho(z,y))\le\phi(\rho(x,z))+\phi(\rho(z,y))$ and skip the intermediate steps in your proof. I might be completely wrong - let me know.

     – Zac Apr 23 '15 at 07:30
  • 1
    @Zac: That's a very nice little trick that you're using to show sub-additivity (the one with $a=a \frac {a+b} {a+b}$), congratulations! I'm jealous for not having thought of it myself. Your proof is entirely correct. – Alex M. Apr 23 '15 at 13:46
0

We have 3 way to prove it,way one:definition of derivation .way two: is mean theorem for sub interval,way three is definition of concave function (this way is hard).we prove from way two :because $\varphi$ is concave then $\varphi^\prime$ is descending ,and apply mean theorem for intervals [0,a] and [b,b+a] assume $0<a<b$ ,for example the function $\sqrt{x}$ is strictly increasing and concave ,(you draw this function for help and apply mean theorem).

amir bahadory
  • 4,629