# Bounding L2 distance with mean and standard deviation

Let $\mathbf{x}=[x_i]_{i=1}^d, \mathbf{y}=[y_i]_{i=1}^d$ be two vectors in $R^d$.

Is it possible to find a lower bound $l\leq \|x-y\|$ and an upper bound $u\geq\|x-y\|$ as a function of $\bar{\mathbf{x}}, \bar{\mathbf{y}}, \sigma({\mathbf x)}$ and $\sigma({\mathbf y})$ ,

where ${\bar v} = \frac{1}{d}\sum_{i=1}^d{v_i}$ and $\sigma(v)=\sqrt{\frac{1}{d}\sum_{i=1}^d{(v_i-\bar v)^2}}$ (the mean and the standard the deviation of $\mathbf{v}$)?

-
What do you mean by mean and standard deviation of two vectors? Don't you mean random variables (vector-valued)? In any case, I don't think so. There is no way to tell if they're equal even if you know the means and standard deviations are the same. –  tomasz Nov 14 '12 at 22:41

This is if I'm not mistaken about your definition of mean and standard deviation.

Provided that $\mathbf{x} = [x_i]_{i=1}^d$ and $\mathbf{y} = [y_i]_{i=1}^d$, the $L_2$ distance between ${\bf x}$ and ${\bf y}$ is $$\|{\bf x} - {\bf y}\|_2 = \sqrt{\sum_i(x_i - y_i)^2}.$$ Using the Minkowski inequality you get $$\|{\bf x} - {\bf y}\|_2 \leq \sqrt{\sum_ix_i^2} + \sqrt{\sum_iy_i^2}.$$ Denoting $\bar{\bf x}$ the mean of ${\bf x}$ and $\sigma({\bf x})$ its standard deviation, by definition $$\sigma({\bf x}) = \sqrt{\frac{1}{d}\sum_ix_i^2 - \bar{\bf x}^2},$$ therefore $$\sqrt{\sum_ix_i^2} = \sqrt{d\left(\sigma({\bf x})^2 + \bar{x}^2\right)}.$$ Finally replace and you get $$\|{\bf x} - {\bf y}\|_2 \leq \sqrt{d}\left( \sqrt{\sigma({\bf x})^2 + \bar{x}^2} + \sqrt{\sigma({\bf y})^2 + \bar{y}^2}\right).$$

-
Thanks! Sorry for the ambiguity in my question, but I'm looking for a lower bound as well. I edited my question to clarify this. –  Ben-Uri Nov 15 '12 at 15:53