3
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
$\begingroup$

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}

$\endgroup$
5
  • $\begingroup$ Can you please explain what you used to go from the second line to the third? $\endgroup$ May 9, 2022 at 9:47
  • 1
    $\begingroup$ @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} $\endgroup$
    – user140541
    May 9, 2022 at 10:12
  • $\begingroup$ 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. $\endgroup$
    – CLL
    May 21, 2022 at 22:00
  • 1
    $\begingroup$ @CLL math.stackexchange.com/questions/63756/tail-sum-for-expectation $\endgroup$
    – user140541
    May 21, 2022 at 22:15
  • $\begingroup$ Makes perfect sense. Thank you @d.k.o. $\endgroup$
    – CLL
    May 21, 2022 at 23:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .