The $\ell_2$ norm of two stochastic vectors

Question

I would like to know why this is true:

Given an $n$-dimensional stochastic vector $v$ and another $n$-dimensional stochastic vector $u$ which distributes uniformly over $\{1,\dots,n\}$ (meaning if the length of the vector $u$ is $n=3$ then $u = (1/3,1/3,1/3)$) then $\lVert u-v\rVert_2 \leq 1$.

For example, let $v = (0.8,0.2)$ and $v = (0.5,0.5)$: $\lVert u-v\rVert_2 = \lVert(0.3,-0.3)\rVert_2=\sqrt{2\cdot0.3^2}$ which is less than 1.

I tried many different inputs and it works for all of them but I can’t figure out why?

Answer 1

First, you can show it will be at most 2 by the triangle inequality, and even a bit better: for $u,v$ two $n$-dimensional vectors in the probability simplex with $u$ being uniform, $$ \lVert u-v\rVert_2 \leq \lVert u\rVert_2+ \lVert v\rVert_2 = \frac{1}{\sqrt{n}} + 1 $$

Now, for the stronger claim. Observe that $$\begin{align} \lVert u-v\rVert_2^2 &= \sum_{k=1}^n (u_k-v_k)^2 = \sum_{k=1}^n u_k^2 + \sum_{k=1}^n v_k^2 - 2\sum_{k=1}^n u_k v_k = n\cdot \frac{1}{n^2} + \lVert v\rVert_2^2 - \frac{2}{n}\sum_{k=1}^n v_k\\ &= \frac{1}{n} + \lVert v\rVert_2^2 - \frac{2}{n} = \lVert v\rVert_2^2 - \frac{1}{n} \\ &\leq 1 - \frac{1}{n} \end{align}$$ where the last inequality comes from the fact that $$\lVert v\rVert_2^2 = \sum_{k=1}^n v_k^2 \leq \sum_{k=1}^n v_k = 1$$ (more generally, $\lVert v\rVert_p \leq \lVert v\rVert_q$ if $p\geq q\geq 1$).

Upshot: the squared $\ell_2$ distance of a probability vector to uniformity is equal, up to an additive factor $1/n$, to its squared $\ell_2$ norm: $$ \lVert u-v\rVert_2^2 = \lVert v\rVert_2^2 - \frac{1}{n} $$ which can itself be interpreted as the collision probability $$ \lVert v\rVert_2^2 = \mathbb{P}_{v}\{ X=Y\} $$ where $X,Y$ are independent random variables with pmf $v$.