# Variational Distance vs. maximum norm

Suppose I have vector $x^t \in \mathbb{R}^n, x_i > 0$ that is a random variable in $t$. I define a measure $D(x) := \max_{i,j} |x_i - x_j|$, which essentially is the maximum discrepancy of any two values in the vector.

A paper I'm currently going through attempts to bound this measure for a certain process. I believe the details are unimportant, except that the sum of all the $x_i$ is $0$ for each $t$.

However, the paper goes on to bound another quantity: The variational distance between vector $x$ and the $0$-vector: $$||x|| = \frac{1}{2} \sum_i |x_i|$$

According to the Wikipedia article on variational distance, the measure $D(x)$ should be the same as the variational distance, but I don't see how this can be the same.

-
They are not: $x=(1,-1)$. – Did Apr 19 '11 at 21:31
Yeah. That's why I'm confused... How can the Wikipedia article (and other literature I found randomly googling for variational distance) claim that they are? – Lagerbaer Apr 20 '11 at 0:17
Well we have $D(x)\leq 2\|x\|?$ if you bound $\|x\|$ then you have bounded $D(x)$ too. Suppose the maximum of $|x_i-x_j|$ happens for $i=1$ and $j=2$ so $$D(x)=|x_1-x_2|\leq |x_1|+|x_2|\leq \sum |x_i|=2\|x\|.$$ – timhortons Apr 20 '11 at 1:03

They are not the same, and the comments show some simple counter-examples. In fact, while $D(x) \leqslant 2 \| x\|$, the gap between these two quantities might be as large as $\Omega(n)$: e.g., take $x$ to be the vector containing $+1$ in half the coordinates, and $-1$ in the remaining half. Then, $D(x) = 2$ while $\| x \| = n/2$.
What is equivalent to the variational distance is a new quantity $D'(x)$ defined as $$D'(x) = \max_{I, J \subseteq [n]} \ | x(I) - x(J) |,$$ where we define $x(I) = \sum \limits_{i \in I} x_i$ (and $x(J)$ similarly). Without loss of generality, we may assume that $I$ and $J$ are disjoint in the above definition.
This satisfies the identity $$D'(x) = 2 \| x \|.$$
Proof. $D'(x) \leqslant \sum_{i} |x_i|$ holds by the triangle inequality. For the other direction, take $I = \{ i \,:\, x_i \geqslant 0 \}$ and $J = [n] \setminus I$. For this choice of $I$ and $J$, it holds that $| x(I) - x(J) | = \sum_i |x_i|$.