# Tail bound implies sub-Gaussian

A random variable $$X$$ is sub-gaussian with parameter $$\sigma^2$$ if for all $$\lambda \in \mathbb{R}$$, we have that $$\mathbb{E} e^{\lambda(X - \mathbb{E} X)} \leq e^{\lambda^2\sigma^2/2}$$

I want to show that if a r.v. $$X$$ satisfies the tail bound: for all $$t \geq 0$$, we have $$P(X - \mathbb{E} X \geq t) \leq e^{-t^2/2\sigma^2} \text{ and } P(X - \mathbb{E} X \leq -t) \leq e^{-t^2/2\sigma^2}$$ then $$X$$ is sub-gaussian with parameter $$c \cdot \sigma^2$$ for some constant $$c$$.

My idea was to use that for a nonnegative random variable $$Z$$ we have that $$\mathbb{E} Z = \int_0^{\infty} P(Z \geq t) \,dt$$ and apply this to $$Z = e^{\lambda(X - \mathbb{E} X)}$$, but this gave a messy integral that I couldn't easily bound with what I wanted, and also only used the first half of the tail bound.

W.l.o.g. assume that $$X$$ is centered, i.e., $$\mathsf{E}X=0$$ (otherwise, condsider $$X'=X-\mathsf{E}X$$). Note that if $$\mathsf{P}(|X|>t)\le 2e^{-t^2/(2\sigma^2)},$$ then $$\mathsf{E}|X|^k\le (2\sigma^2)^{k/2}k\Gamma(k/2)$$ for all integers $$k\ge 1$$. Thus, using the Taylor series for $$\exp(\cdot)$$, for $$\lambda>0$$, \begin{align} \mathsf{E}\exp(\lambda X)&=1+\sum_{k\ge 2}\frac{\lambda^k\mathsf{E}|X|^k}{k!} \\ &\le 1+\sum_{k\ge 2}\frac{\lambda^k (2\sigma^2)^{k/2}k\Gamma(k/2)}{k!} \\ &\le 1+\left(1+\sqrt{\sigma^2\lambda^2/2}\right)\sum_{k\ge 1}\frac{(2\sigma^2\lambda^2)^k}{k!} \\ &= \exp(2\sigma^2\lambda^2)+\sqrt{\sigma^2\lambda^2/2}\left(\exp(2\sigma^2\lambda^2)-1\right) \\ &\le \exp(4\sigma^2\lambda^2). \end{align}

• Can you please explain what you used to go from the second line to the third? May 9, 2022 at 9:47
• @TimHargreaves \begin{align} \sum_{k\ge 2}\frac{\lambda^k (2\sigma^2)^{k/2}k\Gamma(k/2)}{k!}&=\sum_{k\ge 1}\frac{ (2\sigma^2\lambda^2)^{k}(2k)\Gamma(k)}{(2k)!}+\sum_{k\ge 1}\frac{ (2\sigma^2\lambda^2)^{k+1/2}(2k+1)\Gamma(k+1/2)}{(2k+1)!} \\ &\le \left(2+\sqrt{2\sigma^2\lambda^2}\right)\sum_{k\ge 1}\frac{ (2\sigma^2\lambda^2)^{k}k!}{(2k)!} \\ &\le \left(1+\sqrt{\sigma^2\lambda^2/2}\right)\sum_{k\ge 1}\frac{ (2\sigma^2\lambda^2)^{k}}{k!}. \end{align}
– user140541
May 9, 2022 at 10:12
• How does the upper bound on the k-th moment follow from the tail bound? I feel it should be obvious, but I must be missing something.
– CLL
May 21, 2022 at 22:00
• – user140541
May 21, 2022 at 22:15
• Makes perfect sense. Thank you @d.k.o.
– CLL
May 21, 2022 at 23:30