1
$\begingroup$

The variational distance between two probability distributions $X$ and $Y$ taking values on the same alphabet $\mathcal A$ is defined as \begin{equation} \delta (X,Y)=1/2\sum_{a\in A} |p_X(a)-p_Y(a)|$ \end{equation} 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:

\begin{equation} \delta (X,Y)\geq \delta (f(X),f(Y)) \end{equation}

2)

\begin{equation} \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)) \end{equation}

1 Answers 1

4

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

  • 0
    martini: You are welcome. +1.2012-06-21