Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

I got an answer myself:

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

share|improve this question
1  
@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

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.