Definition D1
The data x₁, …, xₙ arranged in order of size are written x₍₁₎ ≤ x₍₂₎ ≤ ⋯ ≤ x₍ₙ₎, and x₍ⱼ₎ is called the j-th order statistic.
Proof.
(1)Σaᵢ denotes a₁ + ⋯ + aₙ, u − v denotes u + (−v), and u ≤ v denotes u < v or u = v.convention
(2)By trichotomy, any two values can always be compared in size.A6
(3)Therefore the smallest of the remaining values can be chosen in turn, and such an arrangement exists.(2), A5
(4)When a value occurs several times there are several arrangements, but the value x₍ⱼ₎ in the j-th position is the same whichever is chosen.(3), A6
∎
Definition D2
When n = 2m + 1, the value in the middle position, x₍ₘ₊₁₎, is called the median, written Me.
Proof.
(1)The middle position is the one with m values before it and m values after it.D1
(2)Below, only the case of odd n is treated.convention
∎
Theorem T1
Let n = 2m + 1 and m ≥ 1. Replacing the maximum x₍ₙ₎ by any t with x₍ₙ₎ ≤ t leaves the median unchanged.
Proof.
(1)After the replacement, the data are x₍₁₎, …, x₍ₙ₋₁₎, t.assumption, D1
(2)If j ≤ n − 1, then x₍ⱼ₎ ≤ x₍ₙ₎ and x₍ₙ₎ ≤ t, so x₍ⱼ₎ ≤ t(1), D1, A5
(3)Therefore x₍₁₎ ≤ ⋯ ≤ x₍ₙ₋₁₎ ≤ t is the new data arranged in order of size.(2), D1
(4)Hence the j-th order statistic of the new data is still x₍ⱼ₎ for j ≤ n − 1.(3), D1
(5)Adding m to both sides of 1 ≤ m gives m + 1 ≤ m + m = 2m = n − 1assumption, A3, A2, N
(6)Therefore the median of the new data is x₍ₘ₊₁₎, the same as the original median.(4), (5), D2
(7)The median of the data 1, 2, 3, 4, 5 is 3, and the median of 1, 2, 3, 4, 1005, obtained by replacing 5 with 1005, is also 3.(6), D2, N
∎
Theorem T2
Under the same operation, the mean can grow without bound.
Proof.
(1)Consider the data 1, 2, 3, 4, t, where t is arbitrary.assumption
(2)Since 1 + 2 + 3 + 4 = 10, the sum of the data is 10 + t.(1), A1, N
(3)Since n = 5, the mean x̄ satisfies 5x̄ = 10 + t.(2), A9, E
(4)If t < t′, then 10 + t < 10 + t′A4
(5)Since 0 < 5, the statements 5x̄ < 5x̄′ and x̄ < x̄′ are equivalent. Hence if t < t′, then x̄ < x̄′(3), (4), A8, A7
(6)If t = 5 then x̄ = 3; if t = 105 then x̄ = 23; if t = 1005 then x̄ = 203.(3), N
(7)Therefore changing a single value can make the mean exceed any bound.(5), (6)
∎
Theorem T3
Let n = 2m + 1. When the top k values are each replaced by values at least x₍ₙ₎, the median is unchanged if k ≤ m, and if k = m + 1 the median can be made larger than any bound.
Proof.
(1)Replace the top k values x₍ₙ₋ₖ₊₁₎, …, x₍ₙ₎ each by a value at least x₍ₙ₎.assumption, D1
(2)The unchanged values are x₍₁₎, …, x₍ₙ₋ₖ₎, all at most x₍ₙ₎, so the replaced values are not smaller than these.(1), D1, A5
(3)Therefore the j-th order statistic of the new data is still x₍ⱼ₎ for j ≤ n − k.(2), D1
(4)Suppose k ≤ m. Adding m + 1 − k to both sides gives m + 1 ≤ 2m + 1 − k = n − kassumption, A3, A1, A2, N
(5)Hence the value in the middle position is still x₍ₘ₊₁₎, and the median is unchanged.(3), (4), D2
(6)Now suppose k = m + 1. Then n − k = 2m + 1 − (m + 1) = m, so only m values are unchanged.assumption, N
(7)If the m + 1 replaced values are all taken larger than some value M, then at most m values in the new data are at most M.(6), assumption
(8)Therefore the (m + 1)-th order statistic exceeds M, and so does the median.(7), D1, D2
(9)To move the median, what matters is not how large the values become but how many are changed, and that count is m + 1.(5), (8)
∎
Corollary C
The mean uses the sizes of the values; the median uses their ranks. The difference in stability comes from here.
Proof.
(1)The mean is determined by n x̄ = Σxᵢ, so it uses every value at its full size. When one value grows, the sum grows by that amount.A9, A4
(2)That is why the maximum alone can push the mean beyond any bound.(1), T2
(3)The median uses not a value but the position m + 1. Whatever the top values become, that position does not change.D1, D2, T1
(4)Moving the position requires not size but count, and that count is m + 1, more than half the data.T3
(5)Therefore the median is stable not because it uses less of the data, but because it uses only order in place of size.(2), (3), (4)
∎