medium vs. mean

任给n个数，证明平均值和中位数的差小于等于标准差
或者给一个随机变量X, 证明
(med(X)-mean(X))^2 <= var(X)


a very classical question. one-side chebychev.

actually, there is a more interesting proof that does not employ
the one-sided chebyshev; which could be understood by almost anyone here.


here it is~

|med(X) - E(X)| <= E|X - med(X)| <= E|X - mean(X)|

<= \sqrt{E|X - mean(X)|^2} <= std(X)

for nonrandom case, the second inequality means that the median minimize L1
error, the last inequality is obtained either by jensen's or by cauchy-
schwarz.

First, we will see why means and medians relate to squares and absolute values. Let x_i be an arbitrary number. Let us define m₂ by the minimization of the sum of squared differences (called the L₂ norm) between m₂ and x_i:

(62)

It is a straight forward task to find the minimum by setting the partial derivative of the sum with respect to m₂ equal to zero. We get

or

(63)

Obviously, m₂ has turned out to be given by the usual definition of mean. Next, let us define m₁ by minimizing the summed absolute values (called the L₁ norm). We have

(64)

To find the minimum we may again set the partial derivative with respect to m₁ equal to zero

(65)

Here the sgn function is +1 when the argument is positive, -1 when the argument is negative, and somewhere in between when the argument is zero. Equation () says that m₁ should be chosen so that m₁ exceeds x_i for N/2 terms, m₁ is less than x_i for N/2 terms, and if there is an x_i left in the middle, m₁ equals that x_i. this defines m₁ as a median. [For an even number N the definition () requires only the m₁ lie anywhere between the middle two values of the x_i.]