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.

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.

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

1 Answer 1

up vote 2 down vote accepted

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|$.

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.