I have been reading from Weak Convergence and Empirical Processes, and came across the following: Let $a_1,\ldots,a_n$ be constants and $\epsilon_1,\ldots,\epsilon_n\sim$Rademacher. Then

$\mathbb{P}\left(\left|\sum_i\epsilon_i a_i\right|>x\right)\leq 2\exp\left(-\frac{x^2}{2||a||^2_2}\right)$

Consequently, $||\sum_i\epsilon_ia_i||_{\Psi_2}\leq\sqrt{6}||a||_2$.

How does this follow (relation between Orlicz norm of Rademacher average and L2 norm of constants)? Thank you in advance for your time.


As I understand these notations, $\Psi_2(x)=\exp(x^2)-1$ and $\|Z\|_{\Psi}=\inf \{c>0 : \mathbb{E} (\Psi(|Z| / c)) \leqslant 1\}$. So the inequality $\|Z\|_{\Psi}\leqslant c$ means that $\mathbb{E} (\Psi(|Z| / c)) \leqslant 1$. Denote $c=\sqrt{6}\|a\|_2$, $Z=|\sum_i \epsilon_i a_i|$. We have $$ \mathbb{E} (\Psi_2(Z/c))=\mathbb{E} \exp(Z^2/c^2)-1=-1+\int_0^\infty\mathbb{P} (\exp(Z^2/c^2)> t)dt=\\ \int_1^\infty\mathbb{P}( Z> c\sqrt{\log t})dt\leqslant \int_1^\infty \min(1,2\exp(-3\log t))dt<2\int_1^\infty t^{-3}dt=1, $$ as we need.

Explanations: we estimated the probability $\mathbb{P}( Z> c\sqrt{\log t})$ from above as $2\exp(-3\log t)$, this is equivalent to $$\mathbb{P}\left(Z>x\right)\leqslant 2\exp\left(-\frac{x^2}{2||a||^2_2}\right)$$ for $x=c\sqrt{\log t}$. Sometimes this is worse than the trivial upper estimate $\mathbb{P}( Z> c\sqrt{\log t})\leqslant 1$, that's why the minimum.

| cite | improve this answer | |
  • $\begingroup$ Thank you. Could you provide a little more explanation behind the last two inequalities? $\endgroup$ – pestopasta May 31 '19 at 17:03
  • 1
    $\begingroup$ @pestopasta done. I replaced max to min as it was supposed to be. $\endgroup$ – Fedor Petrov May 31 '19 at 18:13
  • $\begingroup$ Perfect! Thank you $\endgroup$ – pestopasta May 31 '19 at 18:31

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.