# Variational distance basic properties

The variational distance between two probability distributions $X$ and $Y$ taking values on the same alphabet $\mathcal A$ is defined as $$\delta (X,Y)=1/2\sum_{a\in A} |p_X(a)-p_Y(a)|$$ There are two very basic claims with regard to the variational distance that I would like to formally prove.

1) It cannot increase by the application of a function:

$$\delta (X,Y)\geq \delta (f(X),f(Y))$$

2)

$$\frac{1}{2}\sum_{a\in A} |p_X(a)-p_Y(a)| = 1 -\sum_{a\in A} \min (p_X(a),p_Y(a))$$

-

$\def\abs#1{\left|#1\right|}$ Let $f\colon \mathcal A \to \mathcal A$. Then \begin{align*} \delta\bigl(f(X), f(Y)\bigr) &= \frac 12 \sum_{a \in \mathcal A} \abs{p_{f(X)}(a) - p_{f(Y)}(a)}\\ &= \frac 12 \sum_{a \in \mathcal A} \abs{\sum_{b\in f^{-1}(a)} \bigl(p_X(b) - p_Y(b)\bigr)}\\ &\le \frac 12 \sum_{a \in \mathcal A} \sum_{b \in f^{-1}(a)} \abs{p_X(b) - p_Y(b)}\\ &= \frac 12 \sum_{b \in \mathcal A} \abs{p_X(b) - p_Y(b)}\\ &= \delta(X,Y) \end{align*} Using did's hint from below we have for 2) \begin{align*} \delta(X, Y) &= \frac 12 \sum_{a \in \mathcal A} \abs{p_X(a) - p_{Y}(a)}\\ &= \sum_{a \in \mathcal A} \frac 12 p_X(a) + \frac 12 p_Y(a) - \min\{p_X(a), p_Y(a)\}\\ &= \frac 12 \sum_{a \in \mathcal A} p_X(a) + \frac 12 \sum_{a \in \mathcal A} p_Y(a) - \sum_{a\in \mathcal A} \min\{p_X(a), p_Y(a)\}\\ &= 1 - \sum_{a\in \mathcal A} \min\{p_X(a), p_Y(a)\}. \end{align*}
the last computation could be done faster... Indeed: sum $\frac12|t-s|=\frac12t+\frac12s-\min\{t,s\}$ for $t=p_X(a)$ and $s=p_Y(a)$. – Did Jun 21 '12 at 18:54
@did Thanks. ${}{}{}$ – martini Jun 21 '12 at 19:00