I'm reading the book "Concentration inequalities" by Boucheron, Lugosi, Massart. There is an exercise section after each chapter. I've tried to solve one and would like to understand, whether it would be correct proof or not.

The original task is: Let $MZ$ be a median of the square-integrable random variable $Z$ (i.e. $P\{Z\ge MZ\}\ge\frac{1}{2}$ and $P\{Z\le MZ\}\ge\frac{1}{2}$). Show that $|MZ-EZ|\le\sqrt{Var(Z)}$.

So the solution seems to be simple, my idea is to use Chebyshev's inequality in the following way:

$P\{|X-EX|\ge MX-EX\}\le \frac{Var(X)}{(MX-EX)^2}$. At the same time the probability at the lhs of the inequality is not greater than $1$, i.e.$P\{|X-EX|\ge MX-EX\}\le 1$. Using this, we can write $1 \le \frac{Var(X)}{(MX-EX)^2}$, and therefore $|MX-EX|\le\sqrt{Var(X)}$.

Am I missing something? Also, couple of questions:

  1. Why are we told about square-integrability of $X$? Just to confirm that variance of this variable exists, i.e. $\int (X-\mu)^2f(x)dx$ is bounded?

  2. I have not used the fact that $P\{Z\ge MZ\}\ge\frac{1}{2}$, but it seems like I don't need it. Have I missed something?

Thank you.


1 Answer 1


Your proof is incorrect, since you are arguing that $a\le b$ and $a\le c$ implies that $b\le c$. By your reasoning you could prove that $\operatorname{Var}(X)\ge M^2$ for every $M$, since it "follows" from the fact that $P(|X-EX|>M)\le \frac{\operatorname{Var}(X)}{M^2}$.

For a hint at proving the stated inequality, you can use the fact that the median minimizes $E|Z-c|$ over all $c$, so in particular choose $c:=E(Z)$: $$ E|Z-MZ|\le E|Z-E(Z)|\tag1 $$ Now find a way to relate the LHS of (1) to $|E(Z-MZ)|$ and the RHS of (1) to $\operatorname{Var}(Z)$.

The requirement that $Z$ be square-integrable isn't strictly necessary, since the inequality you are proving becomes vacuous if $\operatorname{Var}(Z)=\infty$.

EDIT: Here is a proof that the median minimizes $E|Z-c|$ over all real $c$.

For simplicity, assume the median is zero (consider $Z':=Z-MZ$). Assume first that $c\ge0$. Argue that in this case, $|y-c|-|y|=c$ when $y\le 0$, and $|y-c|-|y|\ge -c$ when $y>0$, so that $$ E(|Z-c|-|Z|)I(Z\le0)=cP(Z\le0)\tag2$$ and $$E(|Z-c|-|Z|)I(Z>0)\ge -cP(Z>0).\tag3$$ Add (2) and (3) to obtain $$E(|Z-c|-|Z|)\ge c\left[ P(Z\le0)-P(Z>0)\right]=c[2P(Z\le0)-1]\ge0,\tag4$$ the last inequality following from the fact $Z$ has median zero. Conclude $E|Z-0|\le E|Z-c|$. The case $c\le0$ can be reduced to the previous case by considering $-Z$ and $-c$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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