Question

Mean and median. One of the most basic tasks in statistics is to summarize a set of observations ${\mathbf{x}}_{\mathbf{1}}\mathbf{,}{\mathbf{x}}_{\mathbf{2}}\mathbf{,}\mathbf{\dots }\mathbf{,}{\mathbf{x}}_{\mathbf{n}}\mathbf{\subseteq }\mathbf{R}$ by a single number. Two popular choices for this summary statistic are:

• The median, which we’ll call${\mathit{\mu }}_1$

• The mean, which we’ll call${\mathit{\mu }}_{\mathbf{2}}$

(a) Show that the median is the value of $\mathit{\mu }$that minimizes the function

$\mathbf{\sum }_{\mathbf{i}}\mathbf{|}{\mathbf{x}}_{\mathbf{i}}\mathbf{-}\mathbf{\mu }\mathbf{|}$

You can assume for simplicity that is odd. (Hint: Show that for any , the function decreases if you move either slightly to the left or slightly to the right.)

(b) Show that the mean is the value of $\mathit{\mu }$ that minimizes the function

$\mathbf{\sum }_{\mathbf{i}}\mathbf{(}{\mathbf{x}}_{\mathbf{i}}\mathbf{-}\mathbf{\mu }{\mathbf{)}}^{\mathbf{2}}$

One way to do this is by calculus. Another method is to prove that for any $\mathbf{\mu }\mathbf{\in }\mathbf{R}$,

$\mathbf{\sum }_{\mathbf{i}}\mathbf{(}{\mathbf{x}}_{\mathbf{i}}\mathbf{-}\mathbf{\mu }{\mathbf{)}}^{\mathbf{2}}\mathbf{=}\mathbf{\sum }_{\mathbf{i}}\mathbf{(}{\mathbf{x}}_{\mathbf{i}}\mathbf{-}{\mathbf{\mu }}_{\mathbf{2}}{\mathbf{)}}^{\mathbf{2}}\mathbf{+}\mathbf{n}\mathbf{(}\mathbf{\mu }\mathbf{-}{\mathbf{\mu }}_{\mathbf{2}}{\mathbf{)}}^{\mathbf{2}}$

Notice how the function for ${\mathbf{\mu }}_{\mathbf{2}}$ penalizes points that are far from much more heavily than the function for ${\mathbf{\mu }}_1$ . Thus ${\mathbf{\mu }}_{\mathbf{2}}$ tries much harder to be close to all the observations. This might sound like a good thing at some level, but it is statistically undesirable because just a few outliers can severely throw off the estimate of ${\mathbf{\mu }}_{\mathbf{2}}$ . It is therefore sometimes said that ${\mathbf{\mu }}_1$ is a more robust estimator than ${\mathbf{\mu }}_{\mathbf{2}}$ . Worse than either of them, however, is ${\mathit{\mu }}_{\mathbf{\infty }}$ , the value of $\mathit{\mu }$that minimizes the function

$\underset{\mathbf{i}}{\mathbf{max}}\mathbf{|}{\mathbf{x}}_{\mathbf{i}}\mathbf{-}\mathbf{\mu }\mathbf{|}$

(c) Show that ${\mathit{\mu }}_{\mathbf{\infty }}$ can be computed in O(n) time (assuming the numbers are ${\mathbf{x}}_{\mathbf{i}}$small enough that basic arithmetic operations on them take unit time).

Short answer

1. It can be shown that the median is the value of $\mu$ that minimizes the function $\sum _i\left|x_i-\mu \right|$.
2. It can be shown that the median is the value of $\mu$ that minimizes the function $\sum _i{\left(x_i-\mu \right)}^2$.
3. Yes, the ${\mu }_{\infty }$can be computed in O (n) time.

Step-by-step solution

Explain Mean and Median

Mean is the average of all the numbers divided by the total number of the numbers counted. Median is the middle value of the list of the numbers counted for median.

Step 2: Show that the median is the value of   that minimizes the given function

(a)

Consider that the${\mu }^{\text{'}}\ne {\mu }_1.$From the context of a sorted array, there are either more elements to the left $\mu \text{'}$ or to the right. Modify $\mu \text{'}$ to be the element to the right or left , one of the option makes the function described smaller.

If $\mu \text{'}$is moved to the element to the left of it by the amount K. This makes the net difference to the function must either go up or down because $\mu \text{'}$shifted K away from either more or less elements than it shifted K closer to.

By symmetry, Apply this argument to shifting to the right. One of these shifts must increase the function, and the other shift decrease the function.

Therefore, distinctly minimizes the function.

Step 3: Show that the mean is the value of  μ that minimizes the ∑i(xi-μ)2 function

(b) Consider the given function and expand it accordingly.

$$\begin{gathered} \sum _{\mathrm{i}}^{\mathrm{n}}{\left({\mathrm{x}}_{\mathrm{i}}-\mathrm{\mu }\right)}^2=\sum _{\mathrm{i}}^{\mathrm{n}}{\left({\mathrm{x}}_{\mathrm{i}}-{\mathrm{\mu }}_2+\mathrm{\mu }-{\mathrm{\mu }}_2\right)}^2 \\ =\sum _{\mathrm{i}}^{\mathrm{n}}{\left({\left({\mathrm{x}}_{\mathrm{i}}-{\mathrm{\mu }}_2\right)}^2+2\left({\mathrm{x}}_{\mathrm{i}}-{\mathrm{\mu }}_2\right)\left(\mathrm{\mu }-{\mathrm{\mu }}_2\right)+\left(\mathrm{\mu }-{\mathrm{\mu }}_2\right)\right)}^2 \\ =\sum _{\mathrm{i}}^{\mathrm{n}}({\mathrm{x}}_{\mathrm{i}}-{\mathrm{\mu }}_2{)}^2+\mathrm{n}(\mathrm{\mu }-{\mathrm{\mu }}_2{)}^2+2(\mathrm{\mu }-{\mathrm{\mu }}_2)\left(\sum _{\mathrm{i}}^{\mathrm{n}}\left({\mathrm{x}}_{\mathrm{i}}\right)-{\mathrm{n\mu }}_2\right) \\ =\sum _{\mathrm{i}}^{\mathrm{n}}({\mathrm{x}}_{\mathrm{i}}-{\mathrm{\mu }}_2{)}^2+\mathrm{n}(\mathrm{\mu }-{\mathrm{\mu }}_2{)}^2 \end{gathered}$$

Therefore, the given function can be minimized as above.

Step 4: Show that μ∞  can be computed in O(n)  time

(c)

Consider that the numbers $x_i$ are small that the basic arithmetic operations take unit time.

The ${\mu }_{\infty }$,can be computed as follows.

${\mu }_{\infty }=min\left(x_i\right)+\frac{\left(max\right(x_i)-min(x_i\left)\right)}{2}$

The above computation takes the O(n) time since the basic arithmetic operations in the computation takes unit time.