# Why the “distances” satisfy the triangle inequality?

This is a excercise in Shiryaev's Probability On Page 139:

Show that the "distance" $\rho_1(A, B)$ and $\rho_2(A, B)$ defined by $$\rho_1(A, B)=P(A\triangle B),$$ $$\rho_2(A, B)=\begin{cases} \frac{P(A\triangle B)}{P(A\bigcup B)} & \text{if } P(A\bigcup B)\ne 0,\\ \quad\quad\ 0 & \text{if } P(A\bigcup B)=0 \end{cases}$$ satisfy the triangle inequality.

I have proved the case $\rho_1$, but don't know how to prove for $\rho_2$. Thanks!

$$\frac{P(A\Delta C)}{P(A\cup C)}=\frac{P(A\Delta C)}{P(A\Delta C)+P(A\cap B)}\leq \frac{P(A\Delta B)+P(B\Delta C)}{P(A\Delta B)+P(B\Delta C)+P(A\cap B)}$$ Because $(A\Delta B)\cup (B\Delta C) \cup (A\cap B)=A\cup B\cup C$, so $$\frac{P(A\Delta B)+P(B\Delta C)}{P(A\Delta B)+P(B\Delta C)+P(A\cap B)}=\frac{P(A\Delta B)}{P(A\Delta B)+P(B\Delta C)+P(A\cap B)}+\frac{P(B\Delta C)}{P(A\Delta B)+P(B\Delta C)+P(A\cap B)}\\\leq \frac{P(A\Delta B)}{P(A\cup B)}+\frac{P(B\Delta C)}{P(B\cup C)}$$

-
@Danielson : Please notice my edit to your question. The "cases" environment in LaTeX was designed deliberately. –  Michael Hardy Nov 13 '12 at 16:23
@MichaelHardy: Thank you for your edit! –  Danielsen Nov 14 '12 at 3:12
How do you get the first equality in your answer? –  Davide Giraudo Nov 16 '12 at 22:06
Because when $x, \alpha>0$, then$$f(x)=\frac{x}{x+\alpha}=\frac{1}{1+\frac{\alpha}{x}}$$So $f(x)$ is a increasing function. And using the first part of the question, I get the first inequality. –  Danielsen Nov 17 '12 at 3:41

For a more "automatised" solution, one might reason like this:

Fix sets $A,B,C$, and let us show that $\rho_2(A,B) + \rho_2(B,C) \geq \rho_2(A,C)$. These $3$ sets split the space into $7$ pieces (excluding the complement of the sum), and measures of these pieces are essentially independent (essentially, because they still need to sum to at most $1$, but since scaling does not change anything, this does not really matter). Let us give the measures of these pieces some names: $a = P(A\cap B^c \cap C^c),\ b = P(A^c \cap B \cap C^c),\ c = P(A^c \cap B^c \cap C)$, $x = P(A^c \cap B \cap C),\ y = P(A \cap B^c \cap C),\ z = P(A \cap B \cap C^c),\ w = P(A \cap B \cap C)$. Now, $P(A \triangle B) = P(A \cap B^c) + P(A^c \cap B) = a + b + x + y$, while $P(A \cup B) = a + b + x + y + z + w = s - c$, where $s = a + b + c + x + y + z + w$. Thus, $\rho_2(A,B) = \frac{a+b+x+y}{s-c}$.

The claim that the triangle inequality holds now becomes: $$L= \frac{a+b+x+y}{s-c} + \frac{b+c+y+z}{s-a} \geq \frac{c+a+z+x}{s-b} = R$$ This is now "merely" an inquality about positive reals (it is homogenous and we may as well drop the assumption $s \leq 1$), so this should be solvable with a little work.

First, note that except one term, $c$ and $z$ always appear together as $c+z$. If we decrease $c$ and increase $z$, leaving $c+z$ constant, $L$ becomes smaller while $R$ remains fixed. Thus, it will suffice to consider the case when $c$ is as small as possible: $c = 0$. Likewise, we may assume $a = 0$ by decreasing $a$ and keeping $a+x$ constant. Finally, by the same argument applied in reverse, if we decrease $y$ while keeping $b+y$ constant, $R$ increases while $L$ remains constant, so we may assume $y = 0$.

After these simplifications, the inequality under consideration becomes:

$$L= \frac{2b+x+z}{s} = \frac{b+x}{s} + \frac{b+z}{s} \geq \frac{z+x}{s-b} = R$$

Let $t := x+z$ (note that $x$ and $z$ always appear together). The equality we want to prove is equivalent (after multiplying by the denominators) to: $$(2b+t)(s-b) \geq ts$$ After opening the brackets and rearranging once more, this becomes: $$b(2s - 2b - t) \geq 0$$ Because $s = b + x + z + w = b+t+w$, we have $2s \geq 2b + t$, and hence the inequality holds true.

Note: This solution grew a bit longer than initially anticipated. My goal was mainly to show that the problem can be solved in a way which is essentially mechanical, as opposed to the somewhat more inspired solution by the author of the problem.

-