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.

This website does not host notebooks, it only renders notebooks available on other websites.

Delivered by Fastly, Rendered by OVHcloud

nbviewer GitHub repository.

nbviewer version: d25d3c3

nbconvert version: 5.6.1

Rendered (Mon, 27 Jun 2022 09:14:56 UTC)