Derivative-free proof that the median minimizes the sum of absolute differences

Back to main page

Definition (Median)

Let $D=\{x_1,\dots, x_n\}$ be a set of values with $x_1\leq \cdots\leq x_n$. The median of the set is defined to be the following number:

  1. If $n$ is odd and $n=2k+1$ then
$$\text{Median}(D)=x_{k+1}.$$
  1. If $n$ is even and $n=2k$ then
$$\text{Median}(D)=\frac{x_{k}+x_{k+1}}{2}.$$



Theorem.

The minimum of the sum $$g(c)=\sum\limits_{i=1}^n|x_i-c|$$ is attained at the median.

Proof.

Let us take the case of only two points $D=\{x_1, x_2\}$. Using the triangle inequality

$$|x_1-c|+|x_2-c|\geq |x_1-x_2|=x_2-x_1.$$

Moreover, for any $c\in [x_1,x_2]$,

$$|x_1-c|+|x_2-c|=(c-x_1)+(x_2-c)=x_2-x_1.$$

So any point in $[x_1,x_2]$ minimizes $|x_1-c|+|x_2-c|$.

  • When n is even

Then rewrite

$$\sum\limits_{i=1}^{2k}|x_i-c|= \color{blue}{(|x_1-c|+|x_{2k}-c|)}+\color{blue}{(|x_2-c|+|x_{2k-1}-c|)}+\cdots + \color{blue}{(|x_{k}-c|+|x_{k+1}-c|)}$$


According to the discussion above the first term is minimal when $c\in [x_1, x_{2k}]$, the second term is minimal when $c\in [x_2, x_{2k-1}]$ and so on. Thus, when $c\in [x_k,x_{k+1}]$ all the terms have their smallest values. In particular, the median is in that interval: $\frac{x_{k}+x_{k+1}}{2}\in [x_k,x_{k+1}]$ so we have that the median the sum takes its minimal value.

  • When n is odd

Then rewrite

$$\sum\limits_{i=1}^{2k+1}|x_i-c|= \color{blue}{(|x_1-c|+|x_{2k+1}-c|)}+\color{blue}{(|x_2-c|+|x_{2k}-c|)}+\cdots + \color{blue}{(|x_{k}-c|+|x_{k+2}-c|)}+\color{green}{|x_{k+1}-c|}.$$


Again, according to the discussion above the first term is minimal when $c\in [x_1, x_{2k+1}]$, the second term is minimal when $c\in [x_2, x_{2k}]$ and so on. Fiinally, the last term $|x_{k+1}-c|$ is minimal when $c=x_{k+1}$. Thus, when $c=x_{k+1}$ all the terms have their smallest values since it belongs to all the above intervals. And we concude thay the minimal value of their sum is at the median. $\blacksquare$

A more general proof of the theorem can be found in "The theory of probability" by Gnedenko (p. 190) among other places.