Finding median of a given data

Question

We know that minimizing $M= \sum_{i=1}^{n} |X_i -\theta |$ w.r.t. $\theta$ gives us median of the data. The common process is that to choose $\theta$ between $X_{(i)}$ and $X_{(i+1)}$ so that $M$ becomes a continuous function* and then differentiate it. (Here $X_{(i)}$ is the $i$-th order data of the dataset, i.e. $X_{(1)} \leq X_{(2)} \leq \dots \leq X_{(n)}$ .)

*Note that $M=\sum_{j=1}^{i}(-X_{(j)} +\theta )+\sum_{j=i+1}^{n}(X_{(j)} -\theta )$ , then $M$ is continuous, then $\frac{dM}{d\theta} = 0$ gives $\theta =\text{median}$, and $\frac{d^2M}{d\theta^2}>0$. So minimum at median.

But I don't like this process. If there is another way to solve this problem please write the process.

Answer 1

I assume the question is "is there a better way to justify the fact that choosing $\theta$ to be the middle number (or average of the middle two) minimises $\sum_{i=1}^n|X_{(i)}-\theta|$?" If so, the answer is yes.

First look at the first and last terms: $|X_{(1)}-\theta|+|X_{(n)}-\theta|$. If $\theta$ is between $X_{(1)}$ and $X_{(n)}$, then $$|X_{(1)}-\theta|+|X_{(n)}-\theta|=|X_{(1)}-X_{(n)}|,$$ but if it is not between them, then $$|X_{(1)}-\theta|+|X_{(n)}-\theta|>|X_{(1)}-X_{(n)}|,$$ because one of the terms on the LHS is bigger than the RHS.

So we minimise the sum of the first and last terms by taking $\theta$ to be between $X_{(1)}$ and $X_{(n)}$. Similarly, to minimise $|X_{(2)}-\theta|+|X_{(n-1)}-\theta|$ we have to take $\theta$ between $X_{(2)}$ and $X_{(n-1)}$. If we continue in this manner, pairing off all the terms (except the middle term if $n$ is odd), we see that we can minimise all the pairs simultaneously by taking $\theta$ to be inside the middle pair. If $n$ is even we can take any $\theta$ between $X_{(\frac n2)}$ and $X_{(\frac n2+1)}$ and minimise the total sum. If $n$ is odd we still have the final term $|X_{(\frac{n+1}2)}-\theta|$ to deal with: this is clearly minimised by taking $\theta=X_{(\frac{n+1}2)}$, and that also minimises the sums of each of the pairs.

Answer 2

The absolute value function is piecewise linear, with a corner point at $x=0$ and slopes $\mp1$ on either sides.

Then a sum of shifted absolute values is piecewise linear, with corner points at every "shift". Hence, the minimum will arise at a corner point or, in case of zero slope, on the whole interval between two corner points. A priori, there can be several of these.

Furthermore, when you progress from left to right, the slopes go from $-n$ to $+n$ in increments of $2$ as you cross the corner points, and the function is convex. For odd $n$ there will be a single minimum point, and for even $n$, a whole interval.

Note that in case of equal values, the slope will change by $2m$ when crossing them, where $m$ is the multiplicity, but this has no impact on the conclusions.

---

Rigorously working with the derivative is possible.

Actually the function is continuous, and differentiable except at the corner points. In every interval between two corner points, the derivative is a constant so that you know that the function is monotonic. That tells you that the minima inside the intervals occur at an endpoint (or on the whole interval in the degenerate case).

Then as the function is continous, the global minimum will occur where there is a change of sign in the slope. By further discussion of the values of the slope, you show that the change of sign is unique.