3
$\begingroup$

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.

  • 0
    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\|.$2011-04-20

1 Answers 1

2

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