Sub-Gaussian Random Variable

Definition (Sub-Gaussian Random Variable). A random variable $X$ is called a sub-gaussian random variable, if it exhibits one of the following equivalent properties: let $K_i > 0, i \in [5]$ be absolute constants.

1. The tails of $X$ satisfy$$\Pr[|X| \ge t] \le 2 \exp \left(− \frac{t^2}{K_1^2} \right), \quad \forall t \ge 0.$$
2. The moments of $X$ satisfy$$\Vert X \Vert_{L^p} = ( \mathbb{E}|X|^p )^{1/p} \le K_1 \sqrt[p]{p \cdot \Gamma(p / 2)} \le K_2 \sqrt{p}, \quad \forall p \ge 1.$$
3. The MGF of $X^2$ satisfies$$\mathbb{E} \exp(\lambda^2 X^2) \le \exp(K_3^2 \lambda^2) \quad \forall \lambda \, \text{ s.t. }, \, |\lambda| \le 1 / K_3 .$$
4. The MGF of $X^2$ is bounded at some point, namely$$\mathbb{E} \exp(X^2 / K_4^2) \le 2.$$
5. Moreover, if $\mathbb{E} [ X ] = 0$ then properties 1 - 4 are also equivalent to the following property. The MGF of $X$ satisfies$$\mathbb{E} \exp(\lambda X) \le \exp(K_5^2 \lambda^2) \quad \forall \lambda \in \mathbb{R}.$$

Proof.

$1 \rightarrow 2:$

Applying the Stirling's approximation of $\Gamma(x) \le x^x$, and taking the $p$ root of both sides given

$2 \rightarrow 3:$ By monotone convergence theorem,

$3 \rightarrow 4:$ Taking $\lambda = 1 / K_3$ in property 3 proves property 4.

$4 \rightarrow 1:$ By Markov's inequality, we have

$3 \rightarrow 5$ (when $|\lambda| \cdot K_3 \le 1$): Since $e^x \le x + e^{x^2}, \forall x \in R$, we have

$4 \rightarrow 5$ (when $|\lambda| \cdot K_3 \ge 1$): Since $\lambda X \le (X^2 / K_3^2 + \lambda^2 \cdot K_3^2) / 2$, we have

where the final inequality follows as $\lambda^2 K_3^2 \ge 1$.

$5 \rightarrow 1:$ When $\lambda > 0$,

When $\lambda < 0$,

$\square$

Remark. If

$$\mathbb{E} \exp(\lambda X) \le \exp(K_5^2 \lambda^2) \quad \forall \lambda \in \mathbb{R},$$

then it holds that

$$\mathbb{E} [ X ] = 0, \quad \text{ and } \quad \mathbb{E} [ |X|^k ] \in O(k!), \, \forall k \in \mathbb{N}^+.$$

Proof. Since $\exp(|\lambda X|) \le \exp(-\lambda X) + \exp(\lambda X)$, it holds that $\exp(|\lambda X|)$ is integrable and

It follows that $\mathbb{E} \exp(|X|) \in O(1)$. Since $|X|^k \le k! \cdot \exp(|X|)$, it is integrable and

Further, as for each $n \in \mathbb{N}$, it holds that

by dominated convergence theorem, we have

When $|\lambda| < 1$ and $\lambda \rightarrow 0$, clearly

Observe that

Therefore,

Hence,

Taking $\lambda > 0$ and letting $\lambda \rightarrow 0$ gives $\mathbb{E}[X] \le 0$.

Taking $\lambda < 0$ and letting $\lambda \rightarrow 0$ gives $\mathbb{E}[X] \ge 0$.

It concludes that $\mathbb{E} [ X ] = 0$, and therefore $\mathbb{E}[X^2] \le 2 K_5^2$.

$\square$

Definition. The sub-gaussian norm of $X$, denoted $\Vert X \Vert_{\psi_2}$, is defined to be the smallest $K_4$ in property 4, i.e.,

$$\Vert X \Vert_{\psi_2} = \inf \{ t > 0: \mathbb{E} \exp( X^2 / t^2) \le 2 \}.$$

We first show that $\mathbb{E} \exp( X^2 / \Vert X \Vert_{\psi_2}^2) \le 2$. Let $t_1, t_2, t_3, \ldots$ be a decreasing sequence such that $t_i - \Vert X \Vert_{\psi_2} \le 1 / k$. Then by monotone convergence theorem, we have

We restate the previous theorem in terms of the sub-gaussian norm.

1. $\Pr (|X| \ge t) \le 2 \exp( −c t^2 / \Vert X \Vert_{\psi_2} ), \quad \forall t \ge 0$;
2. $\Vert X \Vert_{L_p} \le C \sqrt{p} \Vert X \Vert_{\psi_2}, \quad \forall p \ge 1$
3. $\mathbb{E} \exp(X^2 / \Vert X \Vert_{\psi_2} ) \le 2$;
4. if $\mathbb{E} [ X ] = 0$ then $\mathbb{E} \exp( \lambda X) \le \exp( C \lambda^2 \Vert X \Vert_{\psi_2} ) , \quad \forall \lambda \in \mathbb{R}$.

Here $C, c > 0$ are absolute constants.

Theorem. $\Vert \cdot \Vert_{\psi_2}$ is a norm on the space of sub-gaussian random variables.

Proof. Let $X$ and $Y$ be sub-gaussian random variables, and $a = \Vert X \Vert_{\psi_2}, b = \Vert Y \Vert_{\psi_2}$. Then

Hence,

$\square$

Theorem (Sums of independent sub-gaussians) Let $X_1, \ldots, X_N$ be independent mean-zero sub-gaussian random variables. Then $\sum_{i \in [N]} X_i$ is also a sub-gaussian random variable, and

$$\left\Vert \sum_{i \in [N]} X_i \right\Vert_{\psi_2}^2 \le C \cdot \sum_{i \in [N]} \Vert X \Vert_{\psi_2}^2$$

where $C$ is an absolute constant.

Proof.

Hence, $\sum_{i \in [N]} X_i$ is sug-gaussian, and $\Vert X_i \Vert_{\psi_2}^2 \in O( \sum_{i \in [N]} \Vert X_i \Vert_{\psi_2}^2 )$.

$\square$

Theorem (General Hoeffding Inequality). Let $X_1, \ldots, X_N$ be independent mean-zero sub-gaussian random variables. Then,

$$\Pr \left( \left| \sum_{i \in [N]} X_i \right| \ge t \right) \le 2 \exp \left( − \frac{c t^2}{\sum_{i \in [N]} \Vert X \Vert_{\psi_2}^2} \right), \quad t \ge 0.$$

Proof. This can be viewed as a corollary as the previous theorem.

$\square$

Theorem (Khintchine’s inequality) Let $X_1, \ldots, X_N$ be independent sub-gaussian random variables with zero means and unit variances, and let $a = (a_1,\ldots,a_N) \in \mathbb{R}^N$. Then for every $p \in [2, \infty)$ we have

$$\Vert a \Vert_2 \le \left\Vert \sum_{i \in [N]} a_i X_i \right\Vert_{L_p} \le C K \sqrt{p} \Vert a \Vert_2$$

where $K = \max_i \Vert X_i \Vert_{\psi_2}$ and $C$ is an absolute constant.

Proof. First, since $p \ge 2$, we have

Let $X \doteq \sum_{i \in [N]} a_i X_i$. Then

It follows that

$\square$

Theorem (Centering). If $X$ is a sub-gaussian random variable then $X − \mathbb{E} [ X ]$ is sub-gaussian too and

$$\Vert X − \mathbb{E} [ X ] \Vert_{\psi_2} \le C \Vert X \Vert_{\psi_2},$$

where $C$ is an absolute constant.

Proof. Since $\Vert \cdot \Vert_{\psi_2}$ is a norm,

It remains to bound the second term. By definition, we have

Therefore,

$\square$

Reference

[1] R. Vershynin, High-Dimensional Probability: An Introduction with Applications in Data Science. in Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge: Cambridge University Press, 2018.