Minimizing sum $\sum_{k=1}^n |x_k-a|$, $a=\text{median}_{k}(x_k)$

Question

I was trying to prove some theorem on my way. So the problem was:

Theorem: Let $x_1, x_2, ..., x_n$ be the rising sorted sequence of numbers. The $ \sum_{k=1}^n |x_k-a|$ reaches it minimum if $a=median(x_1, x_2,..., x_n)$.

Proof: First we need to look at that sum if $n=2$. Then we have $$|x_1-a|+|x_2-a|\geqslant|x_2-x_1|=x_2-x_1,$$ because the sequence is rising. So we have that the minimum of that sum is if $$a\in[x_1,x_2]$$ And we know that the median of sequence in that case is really in that interval.

Now let $n$ be any number greater than 2. And lets look first of all at the "boundaries" of the sum, to be more specific $$|x_1-a|+|x_n-a|\geqslant x_n-x_1$$ So as in the case, when $n$ was 2, we get: $$a\in[x_1,x_n]$$

Now let us look some closer parts - $x_2$ and $x_{n-1}$. Repeating our thoughts, we get $$a\in[x_2, x_{n-1}]$$ Which is the sub-interval of the first sum we look it, that means that the $$|x_1-a|+|x_n-a|$$ is still minimal of all possibles. Now we repeat that until we get:

1. if $n=2k$ $$a\in[x_k,x_{k+1}]$$ Where we can find the median.

2. if $n=2k+1$ $$a=x_{k+1}$$ Which is the median.

Now, if we try to get another $a$, suppose $a\in[x_3,x_{n-2}]$, but $a\notin[x_4,x_{n-3}]$, our sum will be the same until $x_4$ but after that it will rise. So if we get any other number the sum will be greater thus this sum reaches its minimum if $a$ is what we get. $\square$

So is this a good proof or I am missing something? Thanks in advance!

Answer 1

Your proof seems perfectly fine, except that you need to prove that $\mid x_1 - a \mid + \mid x_2 - a \mid$ has minimum when $x_1\le a \le x_2$.

Actually all that those subinterval thins are not needed. If $n=2k$ assume that $x_{k} \le a \le x_{k+1}$ and then since the sequence is sorted, we have: $x_i \le a \le x_{n-i+1}$ $\forall i \in [1,k]$. Then from the previous statement we have that all sums $\mid x_i - a \mid + \mid x_{n-i} - a \mid$ are minimized. Now the median of the sequence is $x_{k+1}$, and certainly $x_k\le x_{k+1} \le x_{k+1}$ holds and so all the sums are minimized.

Simularly if $n=2k+1$ set $a=x_{k+1}$ and since $x_i \le a \le x_{n-i+1}$ $\forall i \in [1,k]$, the sums are all minimized and also the lone sum $\mid x_{k+1} - a \mid$ reaches its minimum of 0. Hence the proof.

Answer 2

I like your approach, and it works in principle.

I think you should take a couple of lines at the top to show / state the obvious for the $n=1$ case, that the minimum value of $0$ is obtained at $a=x_1$. Then demonstrate more thoroughly (as Stefan also says) that the minimum value for $n=2$ actually does occurs when $x_1\le a\le x_2$. You could consider at least one case where $a$ is outside this interval and compare.

Your closing statement could also use a little work, it's not entirely clear to me what that is adding.

It has a form that would work well as an inductive proof.