Sub-Gaussian

• Preliminary
  • Gaussian concentration
    The centered Gaussian random variable $X$ on $\mathbb{R}$ with variance $\sigma^2 > 0$ has density given by $$ p(x) = \frac{1}{\sqrt{2\pi\sigma^2}} \text{exp}\left( \frac{-x^2}{2\sigma^2}\right).$$
  • Important propertiy of gaussian
    If $X \sim N(0, \sigma^2)$, we have, for any $t > 0$, $$P(|X| \geq t) \leq \frac{\sigma\sqrt{2}}{t\sqrt{\pi}} \text{exp} \left(\frac{-t^2}{2\sigma^2}\right).$$
  • Proof of above property
    $$ \begin{align}
    P(|X| \geq t) & \leq 2P(X \geq t) \\
    & = \frac{\sqrt{2}}{\sqrt{\pi \sigma^2}} \int^\infty_t \text{exp}\left( \frac{-x^2}{2\sigma^2}\right) dx \\
    & \leq \frac{\sigma^2\sqrt{2}}{\sqrt{\pi \sigma^2}} \int^\infty_t \frac{x}{\sigma^2 t}\text{exp}\left( \frac{-x^2}{2\sigma^2}\right) dx \\
    & = \frac{\sigma\sqrt{2}}{t\sqrt{\pi}} \int^\infty_t -\frac{\partial}{\partial x}\text{exp}\left( \frac{-x^2}{2\sigma^2}\right) dx \\
    & = \frac{\sigma\sqrt{2}}{t\sqrt{\pi}} \text{exp}\left( \frac{-t^2}{2\sigma^2}\right).
    \end{align} $$
• Definition
  A random variable $X \in \mathbb{R}$ is said to be sub-Gaussian with variance proxy $\sigma^2$ if $E[X] = 0$ and its moment generating function satisfies $$ E[\text{exp}(sX)] \leq \text{exp}\left(\frac{\sigma^2 s^2}{2}\right), \forall s \in \mathbb{R}.$$ In this case we write $X \sim \text{subG}(\sigma^2).$
• Equivalent definition
  $$ P(|X| \geq t) \leq 2 \text{exp}(-t^2/C^2), \forall t > 0, \text{ for some constant } C. $$