Given two vectors - $u=(\dfrac{1}{n},\dfrac{1}{n}, ..., \dfrac{1}{n})$ of the uniform distribution on {$1,,...,n$}, and a stochastic vector $p\in \Bbb R^{n}$, I need to show that:
$$\|p-u\|_2\leq1$$
I started with the following step:
$$\|p-u\|_2=\sqrt{(p_1-\dfrac{1}{n})^{2}+(p_2-\dfrac{1}{n})^{2}+(p_3-\dfrac{1}{n})^{2}+...+(p_n-\dfrac{1}{n})^{2}} \leq \sqrt{(1-\dfrac{1}{n})^{2}+(\dfrac{1}{n})^{2}+(\dfrac{1}{n})^{2}+...+\dfrac{1}{n})^{2}} $$
Is this step correct? If not, what am I missing?
On
I don't know if this will be of much use to you, because I don't know how much you know, and what you are just learning.
The function $f:p\mapsto\|p-u\|_2$ is convex, and the set of "stochastic vectors" is closed and convex. You can write $p=\sum p_i e_i$ where the $p_i$ are the entries in $p$ and the $e_i$ are standard unit vectors; then $f(p)\le\sum_i p_if(e_i)$. Or you could argue that $f$ attains its maximum at an extreme point, and that the extreme points are exactly the $e_i$.
If "$p$ is stochastic" is to be interpreted as $p_i\ge 0$ and $\sum_{i=1}^n p_i=1$, then using $p_i\le 1$ one gets $$ \|p-u\|_2^2=\|p\|_2^2-2\langle p,u\rangle+\|u\|_2^2=\sum_{i=1}^n p_i^2-\frac1n \le\sum_{i=1}^n p_i-\frac1n=1-\frac1n<1, $$ so that indeed $$ \|p-u\|_2\le\sqrt{1-\frac1n}<1-\frac{1}{2n}<1 $$