9
$\begingroup$

I have a question similar to this one, but am considering sub-Guassian random variables instead of Gaussian. Let $X_1,\ldots,X_n$ be centered $1$-sub-Gaussian random variables (i.e. $\mathbb{E} e^{\lambda X_i} \le e^{\lambda^2 /2}$), not necessarily independent. I am familiar with the bound $\mathbb{E} \max_i |X_i| \le \sqrt{2 \log (2n)}$, but am looking for an outline of a tail bound for the maximum.

A union bound would give $$\mathbb{P}(\max_i |X_i| > t) \le \sum_i \mathbb{P}(|X_i| > t) \le 2n e^{-t^2/2},$$ but I am looking for a proof of something of the form $$\mathbb{P}(\max_i |X_i| > \sqrt{2 \log (2n)} + t) \le \mathbb{P}(\max_i |X_i| > \mathbb{E} \max_i |X_i| + t) \le 2e^{-t^2/2}.$$ Does anyone have any hints?

$\endgroup$
8
$\begingroup$

I'm not sure but I think this works. Applying the union bound directly gives. \begin{align} \mathbb{P}(\max_i |X_i| > \sqrt{2\log(2n)} + t) &\le 2n \exp\left( -(\sqrt{2\log(2n)}+t)^2/2 \right)\\ &= 2n \exp(-\log (2n) - t\sqrt{2 \log(2n)} - t^2/2)\\ &\le e^{-t\sqrt{2 \log(2n)}} e^{-t^2/2}\\ &\le e^{-t^2/2} \end{align} This is tighter than the bound given in the post I linked in my question, so maybe there I've made a mistake...

$\endgroup$

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.