# Median Concentration implies mean concentrarion

I want to prove that if X is such that $$P[|X-m_X|\geq t] \leq c_1 e^{-c_2t^2},$$ for $$c_1, c_2$$ positive constants, $$t\geq 0$$, then it holds that $$P[|X-E[X]|\geq t] \leq c_3 e^{-c_4t^2},$$ with $$c_3=1+2c_1$$ and $$c_4=c_2/4$$.

There is a proof of reverse direction here.

• see my answer below – mathworker21 Apr 4 at 9:34
• While it does not directly answer your question, you might be interested in this question I just posted: math.stackexchange.com/questions/3609200/… – user2316602 Apr 4 at 9:52
• Edit: I don't think the answer I got uses the specifics of the question at all, so it should answer your question, afterall. – user2316602 Apr 4 at 12:46
• @mathworker21 I can't see your answer below. – Angela Pretorius Apr 5 at 9:37
• Ramon Van Handel's notes on high dimensional probability contain a very similar question 4.2 , with suggested approach : web.math.princeton.edu/~rvan/APC550.pdf – Teresa Lisbon Apr 8 at 12:46

First, note that we may re-write the problem using auxiliary variable $$Y=X-m_X$$. Hence, we need to show,
$$P[|Y|\geq t] \leq c_1 e^{-c_2t^2} \Rightarrow P[|Y-E[Y]|\geq t] \leq c_3 e^{-c_4t^2}.$$
A proof may be obtained using the properties of sub-Gaussian random variables. It can be shown that if $$P[|Y|\geq t] \leq c_1 e^{-c_2t^2}$$ then there exist finite $$c_3,c_4$$ such that $$E[\exp(c_4Y^2)]\leq c_3$$ (You may find the proof in Proposition 2.5.2 of R.Vershynin (2018) book). Hence, $$P[|Y|\geq t] \leq c_1 e^{-c_2t^2} \Rightarrow \exists c_3,c_4>0,\quad E[\exp(c_4Y^2)]\leq c_3.$$ By Markov inequality we may write $$P[|Y-E[Y]|\geq t] = P\left[\exp(c_4|Y-E[Y]|^2)\geq \exp(c_4t^2)\right] \leq e^{-c_4t^2}E\left[\exp(c_4|Y-E[Y]|^2)\right].$$ Then it can be easily seen that: $$e^{-c_4t^2}E\left[\exp(c_4|Y-E[Y]|^2)\right] \leq e^{-c_4t^2}E\left[\exp(c_4|Y|^2)\right],$$ which gives $$P[|Y-E[Y]|\geq t]\leq e^{-c_4t^2}E\left[\exp(c_4|Y|^2)\right]\leq c_3 e^{-c_4t^2}.$$
• Your answer works for every constant instead of $m_X$ as well and is correct. But this is only the first part of proof and in the second part it's important what constant to use, because we should also find the relation between $c_3, c_4$ and $c_1, c_2$ – mohammad Apr 8 at 9:21
• That is true. It works for every constant instead of $m_X$. Preposition 2.5.2 implicitly gives the value of $c_3$ and $c_4$ in terms of $c_1$ and $c_2$, which is difficult to follow. I think some other references on high dimensional probability might have the exact relationship between the constants. – SMA.D Apr 8 at 9:44