Median

The value splitting a sorted sample into two equal parts.

• Also known as — 50th percentile, second quartile (Q2)
• Asymptotic — value where $P(X \leq \operatorname{Median}) = 0.5$
• Complexity — $O(n)$
• Domain — any real numbers
• Unit — same as measurements

Notation

• $x_{(1)}, \ldots, x_{(n)}$ order statistics (sorted sample)

Properties

• Shift equivariance $\operatorname{Median}(\mathbf{x} + k) = \operatorname{Median}(\mathbf{x}) + k$
• Scale equivariance $\operatorname{Median}(k \cdot \mathbf{x}) = k \cdot \operatorname{Median}(\mathbf{x})$

Example

• Median([1, 2, 3, 4, 5]) = 3
• Median([1, 2, 3, 4]) = 2.5

$\operatorname{Median}$ provides maximum protection against outliers and corrupted data. It achieves a 50% breakdown point, meaning that up to half of the data can be arbitrarily bad before the estimate becomes meaningless. However, this extreme robustness comes at a cost: the median is less precise than $\operatorname{Center}$ when data is clean. For most practical applications, $\operatorname{Center}$ offers a better tradeoff (29% breakdown with 95% efficiency). Reserve $\operatorname{Median}$ for situations with suspected contamination levels above 29% or when the strongest possible robustness guarantee is needed.

Algorithm

The $\operatorname{Median}$ algorithm sorts the sample and selects the middle element:

• Sort Arrange the sample to obtain $x_{(1)} \leq x_{(2)} \leq \ldots \leq x_{(n)}$.

• Select If $n$ is odd, return $x_{(\frac{n+1}{2})}$. If $n$ is even, return $\frac{x_{(\frac{n}{2})} + x_{(\frac{n}{2}+1)}}{2}$.

The time complexity is $O(n \log n)$ dominated by the sort. This standard algorithm is used as a building block by other estimators; no specialized implementation is needed beyond the languages built-in sort.

Tests

No reference test data exists for $\operatorname{Median}$ yet. The tests/median/ directory has not been created. Test cases will be added when the $\operatorname{Median}$ test generator is implemented.