0
$\begingroup$

Consider the following (here $x_i,u_i,v_i$ are real numbers): \begin{equation} X=\sum_{x_i\in A}(x_i-\bar{x})^2,\\ U=\sum_{u_i\in B}(u_i-\bar{u})^2,\\ V=\sum_{v_i\in C}(v_i-\bar{v})^2, \end{equation} where $A=B\cup C$ and $B\cap C=\varnothing$ (the empty set) and $\bar{x}$,$\bar{u}$,$\bar{v}$ are the set averages.

How do I show that: $\displaystyle\frac{U+V}{X} \leq 1$ ?

From numerical experimentation it seems that this is true, but I'm not sure on how to proceed to prove this. Extra points for showing that this is true (or not!) for any metric, c.g. replacing $(x_i-\bar{x})^2$ by $g(x_i,\bar{x})$, where $g(\cdot,\cdot)$ is a metric and where $x_i$ can be in $\mathbb{R}^n$.

$\endgroup$

1 Answer 1

0
$\begingroup$

Denote $N_B$ as the number of elements in set $B$ and similarly $N_C$ for set $C$.

One can split set $A$ back into the non-intersecting $B$ and $C$ since $B \cap C = \varnothing$. \begin{align} X &= \sum_{x_i\in B}(x_i - \bar x)^2 + \sum_{x_i\in C}(x_i - \bar x)^2 \\ &= \sum_{x_i\in B}\left( (x_i - \bar u) + (\bar u - \bar x) \vphantom{m^M}\right)^2 + \sum_{x_i\in C}\left( (x_i - \bar v) + (\bar v - \bar x) \vphantom{m^M}\right)^2 \\ &= \sum_{x_i\in B}(x_i - \bar u)^2 + \sum_{x_i\in B} (\bar u - \bar x)^2 + \sum_{x_i\in C}(x_i - \bar v)^2 + \sum_{x_i\in C} (\bar v - \bar x)^2 \\ & \qquad + \left( (\bar u - \bar x) \sum_{x_i\in B} (x_i - \bar u) \right) + \left((\bar v - \bar x) \sum_{x_i\in C} (x_i - \bar v) \right) \\ &= U + N_B (\bar u - \bar x)^2 + V + N_C (\bar v - \bar x)^2 \\ & \qquad + 0 + 0 \end{align} since $\bar u, \bar v, \bar x$ are constants (with respect to the summation) and $$\sum_{x_i\in B} (x_i - \bar u) = \sum_{u_i\in B} (u_i - \bar u) = 0 \qquad \sum_{x_i\in C} (x_i - \bar v) = \sum_{v_i\in C} (v_i - \bar v) = 0$$ by definition of the mean.

In summary, we have $$X = U + V + \text{nonnegative}$$ which is equivalent to the desired inequality.

$\endgroup$
2
  • $\begingroup$ Great, thank you ... that was more straightforward than I thought ... It seems that proving the same, but for $L_1$, i.e replacing $(x_i-\bar{x})^2$ by $|x_i-\bar{x}|$ would be more difficult however... $\endgroup$ Apr 12, 2019 at 15:33
  • $\begingroup$ Indeed, easy decomposition of variance is one of the advantages of mean-square-error. $\endgroup$ Apr 12, 2019 at 15:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .