# Upper bound for the absolute value of an inner product

I am trying to prove the inequality $$\left|\sum\limits_{i=1}^n a_{i}x_{i} \right| \leq \frac{1}{2}(x_{(n)} - x_{(1)}) \sum\limits_{i=1}^n \left| a_{i} \right| \>,$$ where $x_{(n)} = \max_i x_i$ and $x_{(1)} = \min_i x_i$, subject to the condition $\sum_i a_i = 0$.

I've tried squaring and applying Samuelson's inequality to bound the distance between any particular observation and the sample mean, but am making very little headway. I also don't quite understand what's going on with the linear combination of observations out front. Can you guys point me in the right direction on how to get started with this thing?

-
Why is this tagged statistics? – cardinal Jan 20 '13 at 3:36
I guess this is tagged statistics, because this deals with order statistics. – Arin Chaudhuri Jan 20 '13 at 3:38

Hint: $$\left|\sum_i a_i x_i\right| = \frac{1}{2} \left|\sum_i a_i x_i\right| + \frac{1}{2} \left|\sum_i a_i \cdot (-x_i)\right| \>.$$ Now,

1. What do you know about $\sum_i a_i x_{(1)}$ and $\sum_i a_i x_{(n)}$? (Use your assumptions.)
2. Recall the old saw: "There are only three basic operations in mathematics: Addition by zero, multiplication by one, and integration by parts!" (Hint: You won't need the last one.)

Use this and the most basic properties of absolute values and positivity to finish this off.

-
nice, i've added my own solution as well (pretty much the same as yours, minus 1 step). i'd appreciate it if you could check it. – user44429 Jan 20 '13 at 7:05

We have: $$\left|\sum_i a_i x_i\right| = \left|\sum_i a_i(x_i - C)\right|$$ for any constant C. Set $$C:= \frac{1}{2}(x_{(1)} + x_{(n)})$$ Then $$\left| x_{i} - C \right| \leq \frac{1}{2}(x_{(n)} - x_{(1)})$$ and so $$\left|\sum_i a_i x_i\right| = \left | \sum_i (x_{i} - C) a_i \right| \leq \sum_i \left | (x_{i} - C) a_i \right| \leq \sum_i \left | \frac{1}{2}(x_{(n)} - x_{(1)}) a_i \right| = \frac{1}{2}(x_{(n)} - x_{(1)}) \sum_i \left | a_i \right|$$

-
Unfortunately, this argument does not work. Note that since the $a_i$ sum to zero, you've argued that $|\sum_i a_i x_i| \leq 0$, which clearly cannot be the case in general. – cardinal Jan 20 '13 at 14:28
@cardinal ok, how about now? – user44429 Jan 20 '13 at 15:05
Unfortunately, the argument in your new edit is the same (in a slight disguise) as the old. You can't claim $|\sum_i a_i x_i| \leq |\sum_i \frac{1}{2}(x_{(n)}-x_{(1)}) a_i|$ based on what you wrote previously. Indeed, $|\sum_i \frac{1}{2}(x_{(n)}-x_{(1)}) a_i| = 0$. It may help to think through what the absolute value is doing and draw a few diagrams and/or look at some numerical examples. Cheers. :) – cardinal Jan 20 '13 at 23:16
@cardinal ok let's try this again... – user44429 Jan 20 '13 at 23:39
If you replace the third display with $|x_i - C| \leq \frac{1}{2}(x_{(n)} - x_{(1)})$ then the argument works. But, make sure you understand why (and, also, why the suggested change is necessary!), especially as concerns the very last inequality in your post. With that edit, I'll be happy to upvote. Cheers. – cardinal Jan 20 '13 at 23:49