Distance between mean and median

Question

I want to solve the following problem in T.Tao's random matrix theory book. Let $X$ be a random variable with finite second momment. A median $M(X)$ of $X$ saisfies $\mathbb{P}(X>M(X)),\mathbb{P}(X<M(X))\leq 1/2$. Now I wan to prove that for any median: $$M(X)=\mathbb{E}(X)+O((\mathbb{Var}(X))^{1/2})$$

I think we have to use Chebyshev's inequality for this, which I have done to obtain: $$\mathbb{P}(X>\lambda \sigma)\leq \mathbb{P}(|X|>\lambda \sigma)\leq \frac{1}{\lambda ^2}$$ where $\sigma=(\mathbb{Var}(X))^{1/2}$. But I fail to interprete this...

Answer 1

You have to use two things:

1. $\mathbb E(|X-c|)$ is minimized when $c=M(X)$ Proof.

2. Jensen inequality

Then you can have: $$ \left|M(X)-\mathbb{E}(X)\right|=\left|\mathbb{E}(M(X)-X)\right| \\ \leq \mathbb{E}(\left|X-M(X)\right|)\leq \mathbb{E}(\left|X-\mathbb E(X)\right|) \\ \leq \sqrt{\mathbb{E}(\left|X-\mathbb E(X)\right|^2)}=(\mathbb{Var}(X))^{1/2}. $$

Answer 2

Here's a different proof that does not use the fact that $M(X)$ minimizes $c\mapsto E(|X-c|)$.

By Chebyshev’s one-sided inequality (also known as Cantelli's inequality), $$\forall t >0, P\left(\frac{X-E(X)}{\sqrt{Var(X)}}\geq t \right) \leq \frac{1}{1+t^2}$$

Hence, with $t=1$ $$P\left(X\geq E(X)+\sqrt{Var(X)} \right) \leq \frac{1}{2}$$ thus $M(X)\leq E(X)+\sqrt{Var(X)}$.

Replacing $X$ by $-X$ in the previous inequality (this transformation leaves $Var(X)$ untouched), we have $$P(X\leq E(X)-\sqrt{Var(X)})\leq \frac 12$$ thus $M(X)\geq E(X)-\sqrt{Var(X)}$.

Hence $-\sqrt{Var(X)} \leq M(X)-E(X) \leq \sqrt{Var(X)}$, which rewrites as $$|M(X)-E(X)|\leq \sqrt{Var(X)}$$