Tail bound implies sub-Gaussian

924 Views Asked by At

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.

1

There are 1 best solutions below

5
On

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}