I have an exercise that states:

a) Prove that for $0<p<1$, $d_1(x,y) =(|x_1-y_1|^p+|x_2-y_2|^p)^{1/p}$ is not a metric on $\mathbb{R}^2$ and

b) Prove that for $0<p<1$, $d_2(x,y) = |x_1-y_1|^p+|x_2-y_2|^p$ is a metric on $\mathbb{R}^2$

Now obviously the only problem is the triangle inequality. For the first question I found a counter example by taking the points $(1,0)$, $(0,1)$ and $(1,1)$. So this is fine.

I am stuck in the second. How do I prove the triangle inequality for b? I tried to approach it by taking a Taylor series approximation but I got lost very quickly. My second idea was to use the Minkowski inequality but I couldn't apply it somehow. Thanks in advance.

EDIT: corrected the equations

  • 1
    $\begingroup$ b) does not depend on $p$, type? Do you mean $\left(\cdots\right)^p$? $\endgroup$ – user127.0.0.1 Jan 29 '14 at 2:03
  • $\begingroup$ Sorry for the typo, I corrected it. $\endgroup$ – rom Jan 29 '14 at 4:20

I am assuming that for $b)$ you mean:

Prove that for $0 < p < 1,\,$ $d_2(x,y) = \left(|x_1 - y_1| + |x_2 - y_2|\right)^p$ is a metric on $\mathbb{R}^2$.

There are two things you need here:

  • $|x - y| \leq |x| + |y|$.
  • $(a + b)^p \leq a^p + b^p$, for $a,b \geq 0$

This first one is the standard triangle inequality that you are most likely familiar with. To prove the second, you can take the fact that the function $f(x) = x^p$ is convex. What properties you need are:

  • $f(0) = 0$
  • $f'(x) \geq 0$
  • $f''(x) \leq 0$

The first and third of these properties will give you a triangle like inequality:

$$f(a + b) \leq f(a) + f(b).$$

What is this true? Take the difference:

$$ g(x) = f(x + a) - f(x) - f(a) $$

Note that $g'(x) = f'(x + a) - f'(x)$. Since $f''(x) \leq 0$ you must have that $f'$ is decreasing and so $g'(x) \leq 0$. Now take a look at $g(0) = f(a) - f(0) - f(a) = f(0) = 0$. So what you get is $g(x) \leq 0$ for all $x \geq 0$. That is:

$$f(a + b) \leq f(a) + f(b).$$

Now to prove your propositon given these two triangle inequalities is not hard anymore:

Show: $d(x,z) \leq d(x,y) + d(y,z)$. First note that since $f'(x) \geq 0$ you have $f(x) \leq f(y)$ for $x \leq y$. We need this for $(*)$ in the inequality chain. Now get:

$$ \begin{align} d(x,z) & = \left(|x_1 - z_1| + |x_2 - z_2|\right)^p \\ & = \left(|x_1 - y_1 + y_1 - z_1| + |x_2 - y_2 + y_2 - z_2|\right)^p \\ & \leq \left(|x_1 - y_1| + |x_2 - y_2| + |y_1 - z_1| + |y_2 - z_2|\right)^p (*)\\ & \leq \left(|x_1 - y_1| + |x_2 - y_2|\right)^p + \left(|y_1 - z_1| + |y_2 - z_2|\right)^p\\ & = d(x,y) + d(y,z) \end{align} $$

And you are done.

  • $\begingroup$ An easier way to prove your proposition on $(a + b)^p \le a^p + b^p$ is to normalize to $a + b = 1$, then we get that $a^p \ge a$ and $b^p \ge b$ which immediately gives the result. $\endgroup$ – Deven Ware Jan 29 '14 at 3:09
  • $\begingroup$ @DevenWare That's also a great way to go about it, and is in fact how you would go about proving the (harder) Minkowski's inequality. Though, I would say that knowing this technique is helpful for many other triangle inequality problems, especially ones that don't have a homogeneity property. $\endgroup$ – breeden Jan 29 '14 at 3:15
  • $\begingroup$ There was a typo that I corrected. Sorry for that. A question, for $0<p<1$ is $f(s)=x^$ convex? Isn't it concave? But I think that you've actually provided me with the solution. Thanks. $\endgroup$ – rom Jan 29 '14 at 4:25
  • $\begingroup$ @rom, right, sorry. I get to two confused sometimes :) Concave - because it looks more like a cave ;) $\endgroup$ – breeden Jan 29 '14 at 5:04

I assume that you mean:

Prove that for $p\geq 1$ $$d_2(x,y)=\left(|x_1−y_1|^{p}+|x_2−y_2|^{p}\right)^{1/p}$$ is a metric on $\mathbb{R}^2$.

So, the statement of the triangle inequality then becomes: $$ \left(|x_1−y_1|^{p}+|x_2−y_2|^{p}\right)^{1/p}+\left(|y_1−z_1|^{p}+|y_2−z_2|^{p}\right)^{1/p}\geq \left(|x_1−z_1|^{p}+|x_2−z_2|^{p}\right)^{1/p}.$$

Put $\mathbf{u}=\langle x_1-y_1,x_2-y_2\rangle$ and $\mathbf{v}=\langle y_{1}-z_1,y_2-z_2\rangle$, and try rewriting this expression in terms of $p$-norms: $$ \Vert\mathbf{x}\Vert_{p} = \Vert \langle x_{i} ,\ldots x_{n}\rangle\Vert_{p} = \left(\sum_{i=1}^{n}\vert x_{i}\vert^{p} \right)^{1/p}.$$

This should help from here: http://en.wikipedia.org/wiki/Minkowski_inequality

  • $\begingroup$ No, I don't mean this and the Minkowski inequality holds for $p\ge1$, it cannot be applied here directly. $\endgroup$ – rom Jan 29 '14 at 4:19

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.