32
$\begingroup$

Suppose $X$ is a real-valued random variable and let $P_X$ denote the distribution of $X$. Then $$ E(|X-c|) = \int_\mathbb{R} |x-c| dP_X(x). $$ The medians of $X$ are defined as any number $m \in \mathbb{R}$ such that $P(X \leq m) \geq \frac{1}{2}$ and $P(X \geq m) \geq \frac{1}{2}$.

Why do the medians solve $$ \min_{c \in \mathbb{R}} E(|X-c|) \, ? $$

$\endgroup$
27
$\begingroup$

For every real valued random variable $X$, $$ \mathrm E(|X-c|)=\int_{-\infty}^c\mathrm P(X\leqslant t)\,\mathrm dt+\int_c^{+\infty}\mathrm P(X\geqslant t)\,\mathrm dt $$ hence the function $u:c\mapsto \mathrm E(|X-c|)$ is differentiable almost everywhere and, where $u'(c)$ exists, $u'(c)=\mathrm P(X\leqslant c)-\mathrm P(X\geqslant c)$. Hence $u'(c)\leqslant0$ if $c$ is smaller than every median, $u'(c)=0$ if $c$ is a median, and $u'(c)\geqslant0$ if $c$ is greater than every median.

The formula for $\mathrm E(|X-c|)$ is the integrated version of the relations $$(x-y)^+=\int_y^{+\infty}[t\leqslant x]\,\mathrm dt$$ and $|x-c|=((-x)-(-c))^++(x-c)^+$, which yield, for every $x$ and $c$, $$ |x-c|=\int_{-\infty}^c[x\leqslant t]\,\mathrm dt+\int_c^{+\infty}[x\geqslant t]\,\mathrm dt $$

$\endgroup$
  • $\begingroup$ Thanks! (1) By "integrated version", is it to first integrate your last formula wrt $P$ over $\mathbb{R}$, then apply Fubini Thm to exchange the order of the two integrals, and so get the first formula? (2) If temporarily change the notation $P$ to represent the cdf of $X$, is Sivaram's Edit correct? Specifically, do those Riemann-Stieltjes integrals exist? $\endgroup$ – Tim Nov 25 '11 at 8:16
  • $\begingroup$ @Rasmus, you are right, thanks, misprint corrected. $\endgroup$ – Did Nov 25 '11 at 8:21
  • 2
    $\begingroup$ This is a very nice proof. A clarification for future readers, who, like me, would be perplexed by the notation $[x\leq-t]$ and $[x\geq t]$: If $A$ is an event, $[A]$ denotes the indicator function $\mathbb{1}_A$. In particular, $[x\leq-t] = \mathbb{1}_{\{x \leq -t\}}$, and likewise $[x\geq t] = \mathbb{1}_{\{x\geq t\}}$. $\endgroup$ – Evan Aad Oct 18 '16 at 9:31
  • 1
    $\begingroup$ @EvanAad Adding convexity to the pot will allow you to conclude. $\endgroup$ – Did Oct 18 '16 at 16:11
  • 4
    $\begingroup$ @Vim The convexity of the function $u$ makes these objections moot, but here is a more direct route: for every $x$ and $c$, $$ |x-c|=\int_{-\infty}^c[x\leqslant t]\,\mathrm dt+\int_c^{+\infty}[x>t]\,\mathrm dt $$ hence, for every median $m$, $$E(|X-c|)=E(|X-m|)+\int_m^cv(t)dt$$ with $$v(t)=P(X\leqslant t)-P(X>t)=2P(X\leqslant t)-1$$ Then $v$ is nondecreasing and $v(m)\geqslant0$ hence, for every $c>m$, $v\geqslant0$ on $(m,c)$, which implies $E(|X-c|)\geqslant E(|X-m|)$. Likewise for $c<m$. $\endgroup$ – Did Nov 24 '16 at 6:03
6
$\begingroup$

Let $f$ be the pdf and let $J(c) = E(|X-c|)$. We want to maximize $J(c)$. Note that $E(|X-c|) = \int_{\mathbb{R}} |x-c| f(x) dx = \int_{-\infty}^{c} (c-x) f(x) dx + \int_c^{\infty} (x-c) f(x) dx.$

To find the maximum, set $\frac{dJ}{dc} = 0$. Hence, we get that, $$\begin{align} \frac{dJ}{dc} & = (c-x)f(x) | _{x=c} + \int_{-\infty}^{c} f(x) dx + (x-c)f(x) | _{x=c} - \int_c^{\infty} f(x) dx\\ & = \int_{-\infty}^{c} f(x) dx - \int_c^{\infty} f(x) dx = 0 \end{align} $$

Hence, we get that $c$ is such that $$\int_{-\infty}^{c} f(x) dx = \int_c^{\infty} f(x) dx$$ i.e. $$P(X \leq c) = P(X > c).$$

However, we also know that $P(X \leq c) + P(X > c) = 1$. Hence, we get that $$P(X \leq c) = P(X > c) = \frac12.$$

EDIT

When $X$ doesn't have a density, all you need to do is to make use of integration by parts. We get that $$\displaystyle \int_{-\infty}^{c} (c-x) dP(x) = \lim_{y \rightarrow -\infty} (c-y) P(y) + \displaystyle \int_{c}^{\infty} P(x) dx.$$ Similarly, we also get that $$\displaystyle \int_{c}^{\infty} (x-c) dP(x) = \lim_{y \rightarrow \infty} (y-c) P(y) - \displaystyle \int_{c}^{\infty} P(x) dx.$$

$\endgroup$
  • $\begingroup$ Thanks! But does $X$ always have a density? $\endgroup$ – Tim Nov 25 '11 at 7:09
  • $\begingroup$ @Tim: I don't think it is hard to adapt the same idea for the case when $X$ doesn't have a density. $\endgroup$ – user17762 Nov 25 '11 at 7:15
  • $\begingroup$ So you are thinking $P$ as cdf of $X$? $\endgroup$ – Tim Nov 25 '11 at 7:30
3
$\begingroup$

The following intends to complement Did's answer.

Claim

Denote by $M$ be the set of $X$'s medians. Then

  1. $M = [m_1, m_2]$ for some $m_1, m_2 \in \mathbb{R}$, such that $m_1 \leq m_2$.

  2. For every $m \in M$ and for every $x \in \mathbb{R}$ we have $$ E\left(|X-m|\right) \leq E\left(|X-x|\right). $$ (In particular, $m\mapsto E\left(|X-m|\right)$ is constant on $M$.)

Part 2's proof builds on Did's answer.

Proof

  1. It is known that $M \neq \emptyset$. Define $$ \begin{align} M_1 &:= \left\{t\in\mathbb{R}\ |\!:\ F_X(t) \geq \frac{1}{2}\right\}, \\ M_2 &:= \left\{t\in\mathbb{R}\ |\!:\ P(X<t) \leq \frac{1}{2}\right\}. \end{align} $$ Then $M = M_1 \cap M_2$. It therefore suffices to show that $M_1 = [m_1, \infty)$ and that $M_2 = (-\infty, m_2]$, for some $m_1, m_2 \in \mathbb{R}$.

    Since $\lim_{t\rightarrow-\infty}F_X(t) = 0$, $M_1$ is bounded from below. Since $\lim_{t\rightarrow\infty}F_X(t) = 1$, $M_1$ is an interval that extends to infinity. Hence $M_1 = (m_1,\infty)$ or $M_1 = [m_1,\infty)$, for some $m_1 \in \mathbb{R}$. It follows from $F_X$'s right-continuity that $m_1 \in M_1$. An analogous argument shows that $M_2 = (-\infty,m_2]$ (just verify that $t\mapsto P(X<t)$ is left-continuous).

  2. Define a function $f:\mathbb{R}\rightarrow\mathbb{R}$ as follows. For every $c \in \mathbb{R}$, set $$ f(c) := E\left(|X-c|\right). $$

    We will begin by showing that $f$ is convex. Let $a, b \in \mathbb{R}$, and let $t \in (0,1)$. Then $$ \begin{align} f\left(ta+(1-t)b\right) &= E\left(\left|X-\left(ta+(1-t)b\right)\right|\right) \\ &= E\left(\left|\left(tX-ta\right)+\left((1-t)X-(1-t)b\right)\right|\right) \\ &\leq E\left(\left|\left(tX-ta\right)\right|+\left|\left((1-t)X-(1-t)b\right)\right|\right) \\ &=E\left(\left|\left(tX-ta\right)\right|\right)+E\left(\left|\left((1-t)X-(1-t)b\right)\right|\right) \\ &= t\ E\left(|X-a|\right) + (1-t)\ E\left(|X-b|\right) \\ &= t\ f(a) + (1-t)\ f(b). \end{align} $$

    Since $f$ is convex, then, by Theorem 7.40 of [1] (p. 157), there exists a set $A \subseteq \mathbb{R}$ such that $\mathbb{R}\setminus A$ is countable, and such that $f$ is finitely differentiable on $A$. Moreover, letting $m \in M$, and letting $x \in (-\infty, m_1)$, Theorem 7.43 of [1] (p. 158) yields that $f'$ is Lebesgue-integrable on $[x,m] \cap A$, and that $$ f(m) - f(x) = \int_{[x,m]\cap A} f'\ d\lambda. $$

    Applying Did's answer, we find that $f'\leq 0$ on $[x,m]\cap A$. Hence $f(m) \leq f(x)$. Similar considerations show that, for every $x \in (m_2,\infty)$, $f(m) \leq f(x)$, and also that $f(m) = f(m_1)$ (implying that $f$ is constant on $M$, since $m$ was chosen arbitrarily in $M$).

    (The argument of the last paragraph was suggested to me by copper.hat in their answer to a related question of mine.)

Q.E.D.


References

[1] Richard L. Wheeden and Antoni Zygmund. Measure and Integral: An Introduction to Real Analysis. 2nd Ed. 2015. CRC Press. ISBN: 978-1-4987-0290-4.

$\endgroup$
  • $\begingroup$ Thanks. Now I understand why if $M$ is an interval then any point where $f$ assumes zero derivative is a global minimiser of $f$. However, what if $M$ is a singleton and $f$ is not differentiable there? (Also, could you give the name of the Lebesgue integrability theorem you invoked?) $\endgroup$ – Vim Nov 24 '16 at 3:17
  • 1
    $\begingroup$ @Vim: 1. A singleton $\{s\}$ is an interval of the from $[m_1, m_2]$, $m_1\leq m_2$ with $m_1:=m_2:=s$. 2. Here's a link to the theorem. $\endgroup$ – Evan Aad Nov 24 '16 at 9:54
  • $\begingroup$ I was not asking whether a singleton is an interval or not, rather, I was thinking the how to apply the convexity in this case. Anyway it seems already solved to me now: even though $f$ can fail to be differentiable at this point, its left and right derivatives surely exist by convexity, and the left one is $\le 0$ and the right one $\ge 0$ by the definition of the median. $\endgroup$ – Vim Nov 24 '16 at 10:06
  • $\begingroup$ @Vim: My proof covers the case that $M$ is a singleton. $\endgroup$ – Evan Aad Nov 24 '16 at 12:33
  • $\begingroup$ indeed. I had been actually mainly reading the link in your answer, which seemed a bit simpler so that I could grasp it with less knowledge basis. The singleton concern arose from there but not from this answer. $\endgroup$ – Vim Nov 24 '16 at 12:40
3
$\begingroup$

Let $m$ be any median of $X$. Wlog, we can take $m=0$ (consider $X':=X-m$). The aim is to show $E|X-c|\ge E|X|$.

Consider the case $c\ge 0$. It is straightforward to check that $|X-c|-|X|=c$ when $X\le0$, and $|X-c|-|X|\ge -c$ when $X>0$.

It follows that $$ E\left[(|X-c|-|X|)I(X\le0)\right]=cP(X\le0)\tag1 $$ and $$E\left[(|X-c|-|X|)I(X>0)\right]\ge-cP(X>0).\tag2 $$ Adding (1) and (2) yields $$ E(|X-c|-|X|)\ge c\left[P(X\le0)-P(X>0)\right].\tag3 $$ The RHS of (3) equals $c[2P(X\le0)-1]$, which is non-negative since $c\ge0$ and zero is a median of $X$. The case $c\le0$ is reduced to the previous one by considering $X':=-X$ and $c':=-c$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.