9
$\begingroup$

Exercise 2.14 in Wainwright, "High-Dimensional Statistics", states that if $X$ is such that $$P[|X-\mathbb{E}[X]|\geq t] \leq c_1 e^{-c_2t^2},$$ for $c_1, c_2$ positive constants, $t\geq 0$, then for any median $m_X$ it holds that $$P[|X-m_X|\geq t] \leq c_3 e^{-c_4t^2},$$ with $c_3=4c_1$ and $c_4=c_2/8$.

I can get some loose concentration around the median using $|\mathbb{E}[X]-m_X|\leq \sqrt{\mathbb{V}[X]}$, but this does not achieve the constants proposed. Any ideas for how to get the suggested bound, or any other bound resembling it?

$\endgroup$
1
  • 1
    $\begingroup$ In fact the two are equivalent, for example when we use the isoperimetric inequality to prove Poincare type inequalities, we may choose to either infer concentration around the mean or the median. One such technique is used in a proof of the LMSF theorem on norms of Gaussian vectors, in the book of Van Handel $\endgroup$ Mar 16, 2019 at 3:28

1 Answer 1

16
$\begingroup$

Let $\Delta = |EX - m_X|$. The idea of the proof is that if $X$ is too far from mean, then $X$ is far from median as well. If it is close, then make the upper bound a triviality.

Now consider the two cases for $t$:

  1. $t \ge 2\Delta$:

    which implies that $\frac{t}{2} \geq \Delta$. By the reverse triangle inequality, $|X - EX| \geq |X-m_x| - \Delta$. Thus \begin{align} P(|X - m_X|\geq t) \leq P(|X - m_X|\geq \frac{t}{2} + \Delta ) \leq P( |X - EX| \geq \frac{t}{2}) \leq c_1e^{-\frac{c_2t^2}{4}}. \end{align}

  2. $t < 2\Delta$:

    By the definition of median: $\frac{1}{2}\leq P(|X - EX| \geq \Delta ) \leq c_1e^{-c_2\Delta^2}$. Therefore, $2c_1e^{-c_2\Delta^2} \geq 1$. \begin{align} 2c_1e^{-\frac{c_2}{4}t^2} \geq 2c_1e^{-\frac{c_2}{4}(2 \Delta)^2} = 2c_1e^{-c_2\Delta^2} \geq 1 \end{align} Therefore, the required condition holds trivially.

The final constants are $c_3 = 2c_1$ and $c_4 = \frac{c_2}{4}$. I don't know why I am getting better constants. Let me know if you spot an error.

$\endgroup$
4
  • $\begingroup$ The second part of the proof seems to break down when we try to deduce a concentration inequality around the mean from the one around the median. Do you know how to fix this? $\endgroup$ Jul 10, 2019 at 21:09
  • $\begingroup$ Could you provide more details? It might be better to create a separate question for the other way round. $\endgroup$
    – Ankitp
    Dec 30, 2020 at 13:02
  • 2
    $\begingroup$ Why is $P(|X-EX|\ge \Delta)\ge 1/2$? $\endgroup$
    – Alex
    Jan 9, 2021 at 19:09
  • 2
    $\begingroup$ Say $m_X < E X$. Then the set $\{|X - EX| \geq \Delta\}$ includes the set $(-\infty, m_X]$ which has probability mass at least $1/2$ by the definition of the median. The case when $m_X > E X$ is similar. $\endgroup$
    – Ankitp
    Jan 9, 2021 at 23:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .