Sub-Gaussian distribution

The subgaussian norm of $X$, denoted as $\backslash Vert\; X\; \backslash Vert\_\{\backslash psi\_2\}$, is$$\backslash Vert\; X\; \backslash Vert\_\{\backslash psi\_2\}\; =\; \backslash inf\backslash left\backslash \{\; c>0\; :\; \backslash operatorname\{E\}\backslash left[\backslash exp\{\backslash left(\backslash frac\{X^2\}\{c^2\}\backslash right)\}\backslash right]\; \backslash leq\; 2\; \backslash right\backslash \}.$$In other words, it is the Orlicz norm of $X$ generated by the Orlicz function $\backslash Phi(u)=e^\{u^2\}-1.$ By condition $(2)$ below, subgaussian random variables can be characterized as those random variables with finite subgaussian norm.

If there exists some $s^2$ such that $\backslash operatorname\{E\}\; [e^\{(X-\backslash operatorname\{E\}[X])t\}]\; \backslash leq\; e^\{\backslash frac\{s^2t^2\}\{2\}\}$ for all $t$, then $s^2$ is called a variance proxy, and the smallest such $s^2$ is called the optimal variance proxy and denoted by $\backslash Vert\; X\backslash Vert\_\{\backslash mathrm\{vp\}\}^2$.

Since $\backslash operatorname\{E\}\; [e^\{(X-\backslash operatorname\{E\}[X])t\}]\; =\; e^\{\backslash frac\{\backslash sigma^2\; t^2\}\{2\}\}$ when $X\; \backslash sim\; \backslash mathcal\{N\}(\backslash mu,\; \backslash sigma^2)$ is Gaussian, we then have $\backslash |X\backslash |^2\_\{vp\}\; =\; \backslash sigma^2$, as it should.

Let $X$ be a random variable. Let $K\_1,\; K\_2,\; K\_3,\; \backslash dots$ be positive constants. The following conditions are equivalent: (Proposition 2.5.2 {{Cite book |last=Vershynin |first=R. |title=High-dimensional probability: An introduction with applications in data science |publisher=Cambridge University Press |year=2018 |location=Cambridge}})

1. Tail probability bound: $$

\operatorname{P}(|X| \geq t) \leq 2 \exp{(-t^2/K_1^2)}

for all $t\; \backslash geq\; 0$;

1. Finite subgaussian norm: ;
2. Moment: $\backslash operatorname\{E\}\; |X|^p\; \backslash leq\; 2K\_3^p\; \backslash Gamma\backslash left(\backslash frac\{p\}\{2\}+1\backslash right)$ for all $p\; \backslash geq\; 1$, where $\backslash Gamma$ is the Gamma function;
3. Moment: $\backslash operatorname\{E\}|X|^p\backslash leq\; K^p\; p^\{p/2\}$ for all $p\; \backslash geq\; 1$;
4. Moment-generating function (of $X$), or variance proxy{{R|kahane}}{{R|buldygin}} : $\backslash operatorname\{E\}\; [e^\{(X-\backslash operatorname\{E\}[X])t\}]\; \backslash leq\; e^\{\backslash frac\{K^2t^2\}\{2\}\}$ for all $t$;
5. Moment-generating function (of $X^2$): $\backslash operatorname\{E\}[e^\{X^2t^2\}]\; \backslash leq\; e^\{K^2t^2\}$ for all $t\; \backslash in\; [-1/K,\; +1/K]$;
6. Union bound: for some c > 0, $\backslash \; \backslash operatorname\{E\}[\backslash max\backslash \{|X\_1\; -\; \backslash operatorname\{E\}[X]|,\backslash ldots,|X\_n\; -\; \backslash operatorname\{E\}[X]|\backslash \}]\; \backslash leq\; c\; \backslash sqrt\{\backslash log\; n\}$ for all n > c, where $X\_1,\; \backslash ldots,\; X\_n$ are i.i.d copies of X;
7. Subexponential: $X^2$ has a subexponential distribution.

Furthermore, the constant $K$ is the same in the definitions (1) to (5), up to an absolute constant. So for example, given a random variable satisfying (1) and (2), the minimal constants $K\_1,\; K\_2$ in the two definitions satisfy $K\_1\; \backslash leq\; cK\_2,\; K\_2\; \backslash leq\; c\text{'}\; K\_1$, where $c,\; c\text{'}$ are constants independent of the random variable.

As an example, the first four definitions are equivalent by the proof below.

Proof. $(1)\backslash implies(3)$ By the layer cake representation,$$\backslash begin\{align\}$$

\operatorname{E} |X|^p &= \int_0^\infty \operatorname{P}(|X|^p \geq t) dt\\

&= \int_0^\infty pt^{p-1}\operatorname{P}(|X| \geq t) dt\\

&\leq 2\int_0^\infty pt^{p-1}\exp\left(-\frac{t^2}{K_1^2}\right) dt\\

\end{align}

After a change of variables $u=t^2/K\_1^2$, we find that$$\backslash begin\{align\}$$

\operatorname{E} |X|^p &\leq 2K_1^p \frac{p}{2}\int_0^\infty u^{\frac{p}{2}-1}e^{-u} du\\

&= 2K_1^p \frac{p}{2}\Gamma\left(\frac{p}{2}\right)\\

&= 2K_1^p \Gamma\left(\frac{p}{2}+1\right).

\end{align}$(3)\backslash implies(2)$ By the Taylor series $e^x\; =\; 1\; +\; \backslash sum\_\{p=1\}^\backslash infty\; \backslash frac\{x^p\}\{p!\},$$$\backslash begin\{align\}$$

\operatorname{E}[\exp{(\lambda X^2)}] &= 1 + \sum_{p=1}^\infty \frac{\lambda^p \operatorname{E}{[X^{2p}]}}{p!}\\

&\leq 1 + \sum_{p=1}^\infty \frac{2\lambda^p K_3^{2p} \Gamma\left(p+1\right)}{p!}\\

&= 1 + 2 \sum_{p=1}^\infty \lambda^p K_3^{2p}\\

&= 2 \sum_{p=0}^\infty \lambda^p K_3^{2p}-1\\

&= \frac{2}{1-\lambda K_3^2}-1 \quad\text{for }\lambda K_3^2 <1,

\end{align}which is less than or equal to $2$ for $\backslash lambda\; \backslash leq\; \backslash frac\{1\}\{3K\_3^2\}$. Let $K\_2\; \backslash geq\; 3^\{\backslash frac\{1\}\{2\}\}K\_3$, then $\backslash operatorname\{E\}[\backslash exp\{(X^2/K\_2^2)\}]\; \backslash leq\; 2.$

$(2)\backslash implies(1)$ By Markov's inequality,$$\backslash operatorname\{P\}(|X|\backslash geq\; t)\; =\; \backslash operatorname\{P\}\backslash left(\; \backslash exp\backslash left(\backslash frac\{X^2\}\{K\_2^2\}\backslash right)\; \backslash geq\; \backslash exp\backslash left(\backslash frac\{t^2\}\{K\_2^2\}\backslash right)\; \backslash right)\; \backslash leq\; \backslash frac\{\backslash operatorname\{E\}[\backslash exp\{(X^2/K\_2^2)\}]\}\{\backslash exp\backslash left(\backslash frac\{t^2\}\{K\_2^2\}\backslash right)\}\; \backslash leq\; 2\; \backslash exp\backslash left(-\backslash frac\{t^2\}\{K\_2^2\}\backslash right).$$$(3)\; \backslash iff\; (4)$ by asymptotic formula for gamma function: $\backslash Gamma(p/2\; +\; 1\; )\; \backslash sim\; \backslash sqrt\{\backslash pi\; p\}\; \backslash left(\backslash frac\{p\}\{2e\}\; \backslash right)^\{p/2\}$.

From the proof, we can extract a cycle of three inequalities:

• If $$

\operatorname{P}(|X| \geq t) \leq 2 \exp{(-t^2/K^2)}

, then $\backslash operatorname\{E\}\; |X|^p\; \backslash leq\; 2K^p\; \backslash Gamma\backslash left(\backslash frac\{p\}\{2\}+1\backslash right)$ for all $p\; \backslash geq\; 1$.

• If $\backslash operatorname\{E\}\; |X|^p\; \backslash leq\; 2K^p\; \backslash Gamma\backslash left(\backslash frac\{p\}\{2\}+1\backslash right)$ for all $p\; \backslash geq\; 1$, then $\backslash |X\; \backslash |\_\{\backslash psi\_2\}\; \backslash leq\; 3^\{\backslash frac\{1\}\{2\}\}K$.
• If $\backslash |X\; \backslash |\_\{\backslash psi\_2\}\; \backslash leq\; K$, then $$

\operatorname{P}(|X| \geq t) \leq 2 \exp{(-t^2/K^2)}

.

In particular, the constant $K$ provided by the definitions are the same up to a constant factor, so we can say that the definitions are equivalent up to a constant independent of $X$.

Similarly, because up to a positive multiplicative constant, $\backslash Gamma(p/2\; +\; 1)\; =\; p^\{p/2\}\; \backslash times\; ((2e)^\{-1/2\}p^\{1/2p\})^p$ for all $p\; \backslash geq\; 1$, the definitions (3) and (4) are also equivalent up to a constant.

{{Math theorem

| math_statement = * If $X$ is subgaussian, and $k\; >\; 0$, then $\backslash |kX\backslash |\_\{\backslash psi\_2\}\; =\; k\; \backslash |X\backslash |\_\{\backslash psi\_2\}$ and $\backslash |kX\backslash |\_\{vp\}\; =\; k\; \backslash |X\backslash |\_\{vp\}$.

• (Triangle inequality) If $X,\; Y$ are subgaussian, then $$\backslash |X+Y\backslash |\_\{vp\}^2\; \backslash leq\; (\backslash |X\backslash |\_\{vp\}\; +\; \backslash |Y\backslash |\_\{vp\})^2$$

• (Chernoff bound) If $X$ is subgaussian, then $$Pr(X\; \backslash geq\; t)\; \backslash leq\; e^\{-\backslash frac\{t^2\}\{2\backslash |X\backslash |\_\{vp\}^2\}\}$$ for all $t\; \backslash geq\; 0$

| name = Basic properties

}}

$X\; \backslash lesssim\; X\text{'}$ means that $X\; \backslash leq\; CX\text{'}$, where the positive constant $C$ is independent of $X$ and $X\text{'}$.

{{Math theorem

| math_statement = If $X$ is subgaussian, then $$\backslash |X\; -\; E[X]\backslash |\_\{\backslash psi\_2\}\; \backslash lesssim\; \backslash |X\backslash |\_\{\backslash psi\_2\}$$

| name = Subgaussian deviation bound

}}

{{Math proof|title=Proof|proof= By triangle inequality, $\backslash |X\; -\; E[X]\backslash |\_\{\backslash psi\_2\}\; \backslash leq\; \backslash |X\backslash |\_\{\backslash psi\_2\}\; +\; \backslash |E[X]\backslash |\_\{\backslash psi\_2\}$. Now we have $\backslash |E[X]\backslash |\_\{\backslash psi\_2\}\; =\; \backslash sqrt\{\backslash ln\; 2\}\; |E[X]|\; \backslash leq\; \backslash sqrt\{\backslash ln\; 2\}\; E[|X|]\; \backslash sim\; E[|X|]$. By the equivalence of definitions (2) and (4) of subgaussianity, we have $E[|X|]\; \backslash lesssim\; \backslash |X\backslash |\_\{\backslash psi\_2\}$.}}

{{Math theorem

| math_statement = If $X,\; Y$ are subgaussian and independent, then $$\backslash |X+Y\backslash |\_\{vp\}^2\; \backslash leq\; \backslash |X\backslash |\_\{vp\}^2\; +\; \backslash |Y\backslash |\_\{vp\}^2$$

| name = Independent subgaussian sum bound

}}

{{Math proof|title=Proof|proof= If independent, then use that the cumulant of independent random variables is additive. That is, $\backslash ln\; \backslash operatorname\{E\}[e^\{t(X+Y)\}]\; =\; \backslash ln\; \backslash operatorname\{E\}[e^\{tX\}]\; +\; \backslash ln\; \backslash operatorname\{E\}[e^\{tY\}]$.

If not independent, then by Hölder's inequality, for any $1/p\; +\; 1/q\; =\; 1$ we have

$$E[e^\{t(X+Y)\}]\; =\; \backslash |e^\{t(X+Y)\}\backslash |\_1\; \backslash leq\; e^\{\backslash frac\; 12\; t^2\; (p\; \backslash |X\backslash |\_\{vp\}^2\; +\; q\; \backslash |Y\backslash |\_\{vp\}^2)\}$$

Solving the optimization problem

$\backslash begin\{cases\}$

\min p \|X\|_{vp}^2 + q \|Y\|_{vp}^2 \\

1/p + 1/q = 1

\end{cases}, we obtain the result.}}

{{Math theorem

| math_statement = Linear sums of subgaussian random variables are subgaussian.

| name = Corollary

}}

{{Math theorem

| math_statement = If $E[X]\; =\; 0,\; E[X^2]\; =1$, and $-\backslash ln\; Pr(X\; \backslash geq\; t)\; \backslash geq\; \backslash frac\; 12\; at^2$ for all $t\; >0$, then $$\backslash ln\; E[e^\{tX\}]\; \backslash leq\; C\_at^2$$ where $C\_a\; >\; 0$ depends on $a$ only.

| name = Partial converse

| note = Matoušek 2008, Lemma 2.4

}}

{{hidden begin|style=width:100%|ta1=center|border=1px #aaa solid|title=Proof}}

{{Math proof|title=Proof|proof=

Let $F(x)$ be the CDF of $X$. The proof splits the integral of MGF to two halves, one with $tX\; >\; 1$ and one with $tX\; \backslash leq\; 1$, and bound each one respectively.

\begin{aligned}

E[e^{tX}]

&= \int_\R e^{tx} dF(x) \\

&= \int_{-\infty}^{1/t} e^{tx} dF(x) + \int_{1/t}^{+\infty} e^{tx} dF(x) \\

\end{aligned}

Since $e^x\; \backslash leq\; 1+x+x^2$ for $x\; \backslash leq\; 1$, $$$$

\begin{aligned}

\int_{-\infty}^{1/t} e^{tx} dF(x)

&\leq \int_{-\infty}^{1/t} (1+tx + t^2x^2) dF(x) \\

&\leq \int_{\R} (1+tx + t^2x^2) dF(x) \\

&= 1 + tE[X] + t^2 E[X^2] \\

&= 1 + t^2 \\

&\leq e^{t^2}

\end{aligned}

For the second term, upper bound it by a summation: $$$$

\begin{aligned}

\int_{1/t}^{+\infty} e^{tx} dF(x)

&\leq e^2 Pr(X \in [1/t, 2/t]) + e^3 Pr(X \in [1/t, 2/t]) + \dots \\

&\leq \sum_{k=1}^\infty e^{k+1} Pr(X \geq k/t) \\

&\leq \sum_{k=1}^\infty e^{k(2-\frac 12 ak/t^2)}

\end{aligned}

When $t\backslash le\; \backslash sqrt\{a/8\}$, for any $k\backslash ge1$, $2k\; -\; \backslash frac\{a\; k^2\}\{2t^2\}\; \backslash le\; -\backslash frac\{ak\}\{4t^2\}$, so

\leq \frac{1}{e^{\frac{a}{4t^2}} - 1} \leq \frac 4a t^2

When $t>\; \backslash sqrt\{a/8\}$, by drawing out the curve of $f(x)\; =\; e^\{-\backslash frac\{a\}\{2t^2\}x^2\; +\; 2x\}$, and plotting out the summation, we find that $$$$

\sum_{k=1}^\infty e^{k(2-\frac 12 ak/t^2)} \leq \int_\R f(x)dx + 2 \max_x f(x) = e^{\frac{2 t^2}{a}}\left(\sqrt{\frac{2 \pi t^2}{a}}+2\right) < 10 \sqrt{t^2/a} e^{\frac{2 t^2}{a}}

Now verify that , where $C\_a$ depends on $a$ only.

}}{{hidden end}}

{{Math theorem

| name = Corollary

| note = Matoušek 2008, Lemma 2.2

| math_statement = $X\_1,\; \backslash dots,\; X\_n$ are independent random variables with the same upper subgaussian tail: $$$$

-\ln Pr(X_i \geq t) \geq \frac 12 at^2

for all $t>0$. Also, $E[X\_i]\; =\; 0,\; E[X\_i^2]\; =\; 1$, then for any unit vector $v\backslash in\; \backslash R^n$, the linear sum $\backslash sum\_i\; v\_i\; X\_i$ has a subgaussian tail:

-\ln Pr\left(\sum_i v_i X_i \geq t \right) \geq C_a t^2

where $C\_a\; >\; 0$ depends only on $a$.

}}

{{Math theorem|name=Gaussian concentration inequality for Lipschitz functions|note=Tao 2012, Theorem 2.1.12.|math_statement=

If $f:\; \backslash R^n\; \backslash to\; \backslash R$ is $L$-Lipschitz, and $X\; \backslash sim\; N(0,\; I)$ is a standard gaussian vector, then $f(X)$ concentrates around its expectation at a rate $$$$

Pr(f(X) - E[f(X)] \geq t)\leq e^{-\frac{2}{\pi^2}\frac{t^2}{L^2}}

and similarly for the other tail.

}}

{{hidden begin|style=width:100%|ta1=center|border=1px #aaa solid|title=Proof}}

{{Math proof|title=Proof|proof=

By shifting and scaling, it suffices to prove the case where $L\; =\; 1$, and $E[f(X)]\; =\; 0$.

Since every 1-Lipschitz function is uniformly approximable by 1-Lipschitz smooth functions (by convolving with a mollifier), it suffices to prove it for 1-Lipschitz smooth functions.

Now it remains to bound the cumulant generating function.

To exploit the Lipschitzness, we introduce $Y$, an independent copy of $X$, then by Jensen, $$$$

E[e^{t(X-Y)}] = E[e^{tX}]E[e^{-tY}] \geq E[e^{tX}]e^{-tE[Y]} = E[e^{tX}]

By the circular symmetry of gaussian variables, we introduce $X\_\backslash theta\; :=\; Y\backslash cos\backslash theta\; +\; X\backslash sin\backslash theta$. This has the benefit that its derivative $X\text{'}\; =\; -Y\backslash sin\backslash theta\; +\; X\backslash cos\backslash theta$ is independent of it.

$$\backslash begin\{aligned\}e^\{t(f(X)\; -\; f(Y))\}$$

&=e^{t(f(X_{\pi/2}) - f(X_0))} \\

&= e^{t\int_0^{\pi/2} \nabla f(X_\theta) \cdot X_\theta'd\theta} \\

&= e^{\pi t/2 \int_0^{\pi/2} \nabla f(X_\theta) \cdot X_\theta'\frac{d\theta}{\pi/2}} \\

&\leq \int_0^{\pi/2} e^{\pi t/2 \nabla f(X_\theta) \cdot X_\theta'}\frac{d\theta}{\pi/2} \\

\end{aligned}

Now take its expectation, $$$$

E[e^{t(f(X) - f(Y))}] \leq \int_0^{\pi/2} E[e^{\pi t/2 \nabla f(X_\theta) \cdot X_\theta'}]\frac{d\theta}{\pi/2}

The expectation within the integral is over the joint distribution of $X,\; Y$, but since the joint distribution of $X\_\backslash theta,\; X\_\backslash theta\text{'}$ is exactly the same, we have

= E_X[E_Y[e^{\pi t/2 \nabla f(X) \cdot Y}]]

Conditional on $X$, the quantity $\backslash nabla\; f(X)\; \backslash cdot\; Y$ is normally distributed, with variance $\backslash leq\; 1$, so $$$$

\leq e^{\frac 12 (\pi t/2)^2} = e^{\frac{\pi^2}{8} t^2}

Thus, we have $$$$

\ln E[e^{tf(X)}] \leq \frac{\pi^2}{8}t^2

}}{{hidden end}}

Expanding the cumulant generating function:$$\backslash frac\; 12\; s^2\; t^2\; \backslash geq\; \backslash ln\; \backslash operatorname\{E\}[e^\{tX\}]\; =\; \backslash frac\; 12\; \backslash mathrm\{Var\}[X]\; t^2\; +\; \backslash kappa\_3\; t^3\; +\; \backslash cdots$$we find that $\backslash mathrm\{Var\}[X]\; \backslash leq\; \backslash |X\backslash |\_\{\backslash mathrm\{vp\}\}^2$. At the edge of possibility, we define that a random variable $X$ satisfying $\backslash mathrm\{Var\}[X]=\backslash |X\backslash |\_\{\backslash mathrm\{vp\}\}^2$ is called strictly subgaussian.

Theorem.{{cite arXiv |last1=Bobkov |first1=S. G. |title=Strictly subgaussian probability distributions |date=2023-08-03 |eprint=2308.01749 |last2=Chistyakov |first2=G. P. |last3=Götze |first3=F.|class=math.PR }} Let $X$ be a subgaussian random variable with mean zero. If all zeros of its characteristic function are real, then $X$ is strictly subgaussian.

Corollary. If $X\_1,\; \backslash dots,\; X\_n$ are independent and strictly subgaussian, then any linear sum of them is strictly subgaussian.

By calculating the characteristic functions, we can show that some distributions are strictly subgaussian: symmetric uniform distribution, symmetric Bernoulli distribution.

Since a symmetric uniform distribution is strictly subgaussian, its convolution with itself is strictly subgaussian. That is, the symmetric triangular distribution is strictly subgaussian.

Since the symmetric Bernoulli distribution is strictly subgaussian, any symmetric Binomial distribution is strictly subgaussian.

The optimal variance proxy $\backslash Vert\; X\backslash Vert\_\{\backslash mathrm\{vp\}\}^2$ is known for many standard probability distributions, including the beta, Bernoulli, Dirichlet{{R|marchal2017}}, Kumaraswamy, triangular{{R|arbel2020}}, truncated Gaussian, and truncated exponential.{{R|barreto2024}}

Let $p\; +\; q\; =\; 1$ be two positive numbers. Let $X$ be a centered Bernoulli distribution $p\backslash delta\_q\; +\; q\; \backslash delta\_\{-p\}$, so that it has mean zero, then $\backslash Vert\; X\backslash Vert\_\{\backslash mathrm\{vp\}\}^2\; =\; \backslash frac\{p-q\}\{2(\backslash log\; p-\backslash log\; q)\}$. Its subgaussian norm is $t$ where $t$ is the unique positive solution to $pe^\{(q/t)^2\}\; +\; qe^\{(p/t)^2\}\; =\; 2$.

Let $X$ be a random variable with symmetric Bernoulli distribution (or Rademacher distribution). That is, $X$ takes values $-1$ and $1$ with probabilities $1/2$ each. Since $X^2=1$, it follows that$$\backslash Vert\; X\; \backslash Vert\_\{\backslash psi\_2\}\; =\; \backslash inf\backslash left\backslash \{\; c>0\; :\; \backslash operatorname\{E\}\backslash left[\backslash exp\{\backslash left(\backslash frac\{X^2\}\{c^2\}\backslash right)\}\backslash right]\; \backslash leq\; 2\; \backslash right\backslash \}\; =\; \backslash inf\backslash left\backslash \{\; c>0\; :\; \backslash exp\{\backslash left(\backslash frac\{1\}\{c^2\}\backslash right)\}\; \backslash leq\; 2\; \backslash right\backslash \}=\backslash frac\{1\}\{\backslash sqrt\{\backslash ln\; 2\}\},$$and hence $X$ is a subgaussian random variable.

File:Bounded probability distributions, compared with the normal distribution.svg

Bounded distributions have no tail at all, so clearly they are subgaussian.

If $X$ is bounded within the interval $[a,\; b]$, Hoeffding's lemma states that $\backslash Vert\; X\backslash Vert\_\{\backslash mathrm\{vp\}\}^2\; \backslash leq\; \backslash left(\backslash frac\{b-a\}\{2\}\backslash right)^2$. Hoeffding's inequality is the Chernoff bound obtained using this fact.

File:Gaussian-mixture-example.svg

Since the sum of subgaussian random variables is still subgaussian, the convolution of subgaussian distributions is still subgaussian. In particular, any convolution of the normal distribution with any bounded distribution is subgaussian.

Given subgaussian distributions $X\_1,\; X\_2,\; \backslash dots,\; X\_n$, we can construct an additive mixture $X$ as follows: first randomly pick a number $i\; \backslash in\; \backslash \{1,\; 2,\; \backslash dots,\; n\backslash \}$, then pick $X\_i$.

Since $\backslash operatorname\{E\}\backslash left[\backslash exp\{\backslash left(\backslash frac\{X^2\}\{c^2\}\backslash right)\}\backslash right]\; =\; \backslash sum\_i\; p\_i\; \backslash operatorname\{E\}\backslash left[\backslash exp\{\backslash left(\backslash frac\{X\_i^2\}\{c^2\}\backslash right)\}\backslash right]$we have $\backslash |X\backslash |\_\{\backslash psi\_2\}\; \backslash leq\; \backslash max\_i\; \backslash |X\_i\backslash |\_\{\backslash psi\_2\}$, and so the mixture is subgaussian.

In particular, any gaussian mixture is subgaussian.

More generally, the mixture of infinitely many subgaussian distributions is also subgaussian, if the subgaussian norm has a finite supremum: $\backslash |X\backslash |\_\{\backslash psi\_2\}\; \backslash leq\; \backslash sup\_i\; \backslash |X\_i\backslash |\_\{\backslash psi\_2\}$.

So far, we have discussed subgaussianity for real-valued random variables. We can also define subgaussianity for random vectors. The purpose of subgaussianity is to make the tails decay fast, so we generalize accordingly: a subgaussian random vector is a random vector where the tail decays fast.

Let $X$ be a random vector taking values in $\backslash R^n$.

Define.

• $\backslash |X\backslash |\_\{\backslash psi\_2\}\; :=\; \backslash sup\_\{v\; \backslash in\; S^\{n-1\}\}\backslash |v^T\; X\backslash |\_\{\backslash psi\_2\}$, where $S^\{n-1\}$ is the unit sphere in $\backslash R^n$. Similarly for the variance proxy $\backslash |X\backslash |\_\{vp\}\; :=\; \backslash sup\_\{v\; \backslash in\; S^\{n-1\}\}\backslash |v^T\; X\backslash |\_\{vp\}$
• $X$ is subgaussian iff .

Theorem. (Theorem 3.4.6 ) For any positive integer $n$, the uniformly distributed random vector $X\; \backslash sim\; U(\backslash sqrt\{n\}\; S^\{n-1\})$ is subgaussian, with $\backslash |X\backslash |\_\{\backslash psi\_2\}\; \backslash lesssim\{\}\; 1$.

This is not so surprising, because as $n\; \backslash to\; \backslash infty$, the projection of $U(\backslash sqrt\{n\}\; S^\{n-1\})$ to the first coordinate converges in distribution to the standard normal distribution.

{{Math theorem

| math_statement =

If $X\_1,\; \backslash dots,\; X\_n$ are mean-zero subgaussians, with $\backslash |X\_i\; \backslash |\_\{vp\}^2\; \backslash leq\; \backslash sigma^2$, then for any $\backslash delta\; >\; 0$, we have $\backslash max(X\_1,\; \backslash dots,\; X\_n)\; \backslash leq\; \backslash sigma\backslash sqrt\{2\; \backslash ln\; \backslash frac\{n\}\{\backslash delta\}\}$ with probability $\backslash geq\; 1-\backslash delta$.

}}

{{Math proof|title=Proof|proof= By the Chernoff bound, $\backslash Pr(X\_i\; \backslash geq\; \backslash sigma\; \backslash sqrt\{2\; \backslash ln(n/\backslash delta)\})\; \backslash leq\; \backslash delta/n$. Now apply the union bound. }}

{{Math theorem

| note=Exercise 2.5.10

| math_statement = If $X\_1,\; X\_2,\; \backslash dots$ are subgaussians, with $\backslash |X\_i\; \backslash |\_\{\backslash psi\_2\}\; \backslash leq\; K$, then $$E\backslash left[\backslash sup\_n\; \backslash frac$$

}}

{{Math theorem

| math_statement = If $X\_1,\; \backslash dots,\; X\_n$ are subgaussian, with $\backslash |X\_i\; \backslash |\_\{vp\}^2\; \backslash leq\; \backslash sigma^2$, then$$\backslash begin\{aligned\}$$

E[\max_i (X_i - E[X_i])] \leq \sigma\sqrt{ 2\ln n}, &\quad \Pr(\max_i (X_i- E[X_i]) > t) \leq n e^{-\frac{t^2}{2\sigma^2}}, \\

E[\max_i |X_i - E[X_i]|] \leq \sigma\sqrt{ 2\ln (2n)},

&\quad

\Pr(\max_i |X_i- E[X_i]| > t) \leq 2 n e^{-\frac{t^2}{2\sigma^2}}

\end{aligned}

| note = over a finite set{{Cite web |title=MIT 18.S997 {{!}} Spring 2015 {{!}} High-Dimensional Statistics, Chapter 1. Sub-Gaussian Random Variables |url=https://ocw.mit.edu/courses/18-s997-high-dimensional-statistics-spring-2015/a69e2f53bb2eeb9464520f3027fc61e6_MIT18_S997S15_Chapter1.pdf |access-date=2024-04-03 |website=MIT OpenCourseWare |language=en}}

}}

{{Math proof|title=Proof|proof= For any t>0:$$\backslash begin\{aligned\}$$

E\!\bigl[\max_{1\le i\le n}(X_i-E[X_i])\bigr]

&=\frac1t\,E\!\Bigl[\ln\max_{i}e^{\,t(X_i-E[X_i])}\Bigr]\\

&\le\frac1t\ln E\!\Bigl[\max_{i}e^{\,t(X_i-E[X_i])}\Bigr] \quad \text{by Jensen}\\

&\le\frac1t\ln\sum_{i=1}^{n}Ee^{t(X_i-E[X_i])}\\

&\le\frac1t\ln\sum_{i=1}^{n}e^{\sigma^{2}t^{2}/2}\quad \text{by def of }\|\cdot\|_{vp}\\

&=\frac{\ln n}{t}+\frac{\sigma^{2}t}{2} \\

&\overset{t=\sqrt{2\ln n}/\sigma}{=}\;\sigma\sqrt{2\ln n},

\end{aligned}This is a standard proof structure for proving Chernoff-like bounds for sub-Gaussian variables. For the second equation, it suffices to prove the case with one variable and zero mean, then use the union bound. First by Markov, $\backslash Pr(X\; >\; t)\; \backslash leq\; \backslash Pr(e^\{sX\}\; >\; e^\{st\})\; \backslash leq\; e^\{-st\}\; E[e^\{sX\}]$

, then by definition of variance proxy, $\backslash leq\; e^\{-st\}\; e^\{\backslash sigma^2s^2/2\}$

, and then optimize at $s\; =\; -t^2/2\backslash sigma^2$

.

}}

{{Math theorem

| math_statement = Fix a finite set of vectors $v\_1,\; \backslash dots,\; v\_n$. If $X$ is a random vector, such that each $\backslash |\; v\_i^T\; X\; \backslash |\_\{vp\}^2\; \backslash leq\; \backslash sigma^2$, then the above 4 inequalities hold, with $\backslash max\_\{v\; \backslash in\; \backslash mathrm\{conv\}(v\_1,\; \backslash dots,\; v\_n)\}(v^T\; X\; -\; E[v^T\; X])$ replacing $\backslash max\_i\; (X\_i\; -\; E[X\_i])$. Here, $\backslash mathrm\{conv\}(v\_1,\; \backslash dots,\; v\_n)$ is the convex polytope hulled by the vectors $v\_1,\; \backslash dots,\; v\_n$.

| note = over a convex polytope

| name=Corollary

}}

{{Math theorem

| math_statement = If $X$ is a random vector in $\backslash R^d$, such that $\backslash |v^T\; X\backslash |\_\{vp\}^2\; \backslash leq\; \backslash sigma^2$ for all $v$ on the unit sphere $S$, then $$E[\backslash max\_\{v\; \backslash in\; S\}\; v^T\; X]\; =\; E[\backslash max\_\{v\; \backslash in\; S\}\; |v^T\; X|]\; \backslash leq\; 4\backslash sigma\; \backslash sqrt\{d\}$$For any $\backslash delta\; >\; 0$, with probability at least $1-\backslash delta$,$$\backslash max\_\{v\; \backslash in\; S\}\; v^T\; X\; =\; \backslash max\_\{v\; \backslash in\; S\}\; |\; v^T\; X\; |\; \backslash leq\; 4\; \backslash sigma\; \backslash sqrt\{d\}+2\; \backslash sigma\; \backslash sqrt\{2\; \backslash log\; (1\; /\; \backslash delta)\}$$

| note = subgaussian random vectors

}}

Theorem. (Theorem 2.6.1 ) There exists a positive constant $C$ such that given any number of independent mean-zero subgaussian random variables $X\_1,\; \backslash dots,X\_n$, $$\backslash left\backslash |\backslash sum\_\{i=1\}^n\; X\_i\backslash right\backslash |\_\{\backslash psi\_2\}^2\; \backslash leq\; C\; \backslash sum\_\{i=1\}^n\backslash left\backslash |X\_i\backslash right\backslash |\_\{\backslash psi\_2\}^2$$Theorem. (Hoeffding's inequality) (Theorem 2.6.3 ) There exists a positive constant $c$ such that given any number of independent mean-zero subgaussian random variables $X\_1,\; \backslash dots,X\_N$,$$\backslash mathbb\{P\}\backslash left(\backslash left|\backslash sum\_\{i=1\}^N\; X\_i\backslash right|\; \backslash geq\; t\backslash right)\; \backslash leq\; 2\; \backslash exp\; \backslash left(-\backslash frac\{c\; t^2\}\{\backslash sum\_\{i=1\}^N\backslash left\backslash |X\_i\backslash right\backslash |\_\{\backslash psi\_2\}^2\}\backslash right)$$

\quad \forall t > 0Theorem. (Bernstein's inequality) (Theorem 2.8.1 ) There exists a positive constant $c$ such that given any number of independent mean-zero subexponential random variables $X\_1,\; \backslash dots,X\_N$,$$\backslash mathbb\{P\}\backslash left(\backslash left|\backslash sum\_\{i=1\}^N\; X\_i\backslash right|\; \backslash geq\; t\backslash right)\; \backslash leq\; 2\; \backslash exp\; \backslash left(-c\; \backslash min\; \backslash left(\backslash frac\{t^2\}\{\backslash sum\_\{i=1\}^N\backslash left\backslash |X\_i\backslash right\backslash |\_\{\backslash psi\_1\}^2\},\; \backslash frac\{t\}\{\backslash max\; \_i\backslash left\backslash |X\_i\backslash right\backslash |\_\{\backslash psi\_1\}\}\backslash right)\backslash right)$$

Theorem. (Khinchine inequality) (Exercise 2.6.5 ) There exists a positive constant $C$ such that given any number of independent mean-zero variance-one subgaussian random variables $X\_1,\; \backslash dots,X\_N$, any $p\; \backslash geq\; 2$, and any $a\_1,\; \backslash dots,\; a\_N\; \backslash in\; \backslash R$,$$\backslash left(\backslash sum\_\{i=1\}^N\; a\_i^2\backslash right)^\{1\; /\; 2\}\; \backslash leq\backslash left\backslash |\backslash sum\_\{i=1\}^N\; a\_i\; X\_i\backslash right\backslash |\_\{L^p\}\; \backslash leq\; C\; K\; \backslash sqrt\{p\}\backslash left(\backslash sum\_\{i=1\}^N\; a\_i^2\backslash right)^\{1\; /\; 2\}$$

The Hanson-Wright inequality states that if a random vector $X$ is subgaussian in a certain sense, then any quadratic form $A$ of this vector, $X^TAX$, is also subgaussian/subexponential. Further, the upper bound on the tail of $X^TAX$, is uniform.

A weak version of the following theorem was proved in (Hanson, Wright, 1971).{{Cite journal |last1=Hanson |first1=D. L. |last2=Wright |first2=F. T. |date=1971 |title=A Bound on Tail Probabilities for Quadratic Forms in Independent Random Variables |journal=The Annals of Mathematical Statistics |volume=42 |issue=3 |pages=1079–1083 |doi=10.1214/aoms/1177693335 |jstor=2240253 |issn=0003-4851|doi-access=free }} There are many extensions and variants. Much like the central limit theorem, the Hanson-Wright inequality is more a cluster of theorems with the same purpose, than a single theorem. The purpose is to take a subgaussian vector and uniformly bound its quadratic forms.

Theorem.{{Cite journal |last1=Rudelson |first1=Mark |last2=Vershynin |first2=Roman |date=January 2013 |title=Hanson-Wright inequality and sub-gaussian concentration |url=https://projecteuclid.org/journals/electronic-communications-in-probability/volume-18/issue-none/Hanson-Wright-inequality-and-sub-gaussian-concentration/10.1214/ECP.v18-2865.full |journal=Electronic Communications in Probability |volume=18 |issue=none |pages=1–9 |doi=10.1214/ECP.v18-2865 |issn=1083-589X|arxiv=1306.2872 }}{{Cite book |last=Vershynin |first=Roman |url=https://www.cambridge.org/core/books/highdimensional-probability/797C466DA29743D2C8213493BD2D2102 |title=High-Dimensional Probability: An Introduction with Applications in Data Science |date=2018 |publisher=Cambridge University Press |isbn=978-1-108-41519-4 |series=Cambridge Series in Statistical and Probabilistic Mathematics |location=Cambridge |chapter=6. Quadratic Forms, Symmetrization, and Contraction |pages=127–146 |doi=10.1017/9781108231596.009 |chapter-url=https://doi.org/10.1017/9781108231596.009}} There exists a constant $c$, such that:

Let $n$ be a positive integer. Let $X\_1,\; ...,\; X\_n$ be independent random variables, such that each satisfies $E[X\_i]\; =\; 0$. Combine them into a random vector $X\; =\; (X\_1,\; \backslash dots,\; X\_n)$. For any $n\backslash times\; n$ matrix $A$, we have$$P(|X^T\; AX\; -\; E[X^TAX]|\; >\; t\; )\; \backslash leq\; \backslash max\backslash left(\; 2\; e^\{-\backslash frac\{ct^2\}\{K^4\backslash |A\backslash |\_F^2\}\},\; 2\; e^\{-\backslash frac\{ct\}\{K^2\backslash |A\backslash |\}\}\; \backslash right)\; =$$

2 \exp \left[-c \min \left(\frac{t^2}{K^4\|A\|_F^2}, \frac{t}{K^2\|A\|}\right)\right]

where $K\; =\; \backslash max\_i\; \backslash |X\_i\backslash |\_\{\backslash psi\_2\}$, and $\backslash |A\backslash |\_F\; =\; \backslash sqrt\{\backslash sum\_\{ij\}\; A\_\{ij\}^2\}$ is the Frobenius norm of the matrix, and $\backslash |A\backslash |\; =\; \backslash max\_\{\backslash |x\backslash |\_2=1\}\; \backslash |Ax\backslash |\_2$ is the operator norm of the matrix.

In words, the quadratic form $X^TAX$ has its tail uniformly bounded by an exponential, or a gaussian, whichever is larger.

In the statement of the theorem, the constant $c$ is an "absolute constant", meaning that it has no dependence on $n,\; X\_1,\; \backslash dots,\; X\_n,\; A$. It is a mathematical constant much like pi and e.

Theorem (subgaussian concentration). There exists a constant $c$, such that:

Let $n,\; m$ be positive integers. Let $X\_1,\; ...,\; X\_n$ be independent random variables, such that each satisfies $E[X\_i]\; =\; 0,\; E[X\_i^2]\; =\; 1$. Combine them into a random vector $X\; =\; (X\_1,\; \backslash dots,\; X\_n)$. For any $m\backslash times\; n$ matrix $A$, we have$$P(\; |\; \backslash |\; AX\backslash |\_2\; -\; \backslash |A\backslash |\_F\; |\; >\; t\; )\; \backslash leq\; 2\; e^\{-\backslash frac\{ct^2\}\{K^4\backslash |A\backslash |^2\}\}$$In words, the random vector $A\; X$ is concentrated on a spherical shell of radius $\backslash |A\; \backslash |\_F$, such that $\backslash |\; AX\backslash |\_2\; -\; \backslash |A\; \backslash |\_F$ is subgaussian, with subgaussian norm $\backslash leq\; \backslash sqrt\{3/c\}\; \backslash |A\backslash |\; K^2$.

• Platykurtic distribution

{{reflist|refs=

Wainwright MJ. High-Dimensional Statistics: A Non-Asymptotic Viewpoint. Cambridge: Cambridge University Press; 2019. {{doi|10.1017/9781108627771}}, {{ISBN|9781108627771}}.

{{cite journal | doi=10.4064/sm-19-1-1-25 | title=Propriétés locales des fonctions à séries de Fourier aléatoires | date=1960 | last1=Kahane | first1=J. | journal=Studia Mathematica | volume=19 | pages=1–25 }}

{{cite journal | doi=10.1007/BF01087176 | title=Sub-Gaussian random variables | date=1980 | last1=Buldygin | first1=V. V. | last2=Kozachenko | first2=Yu. V. | journal=Ukrainian Mathematical Journal | volume=32 | issue=6 | pages=483–489 }}

{{cite journal | doi=10.1214/17-ECP92 | title=On the sub-Gaussianity of the Beta and Dirichlet distributions | date=2017 | last1=Marchal | first1=Olivier | last2=Arbel | first2=Julyan | journal=Electronic Communications in Probability | volume=22 | arxiv=1705.00048 }}

{{cite journal | doi=10.1051/ps/2019018 | title=On strict sub-Gaussianity, optimal proxy variance and symmetry for bounded random variables | date=2020 | last1=Arbel | first1=Julyan | last2=Marchal | first2=Olivier | last3=Nguyen | first3=Hien D. | journal=Esaim: Probability and Statistics | volume=24 | pages=39–55 | arxiv=1901.09188 }}

{{cite arXiv | eprint=2403.08628 | last1=Barreto | first1=Mathias | last2=Marchal | first2=Olivier | last3=Arbel | first3=Julyan | title=Optimal sub-Gaussian variance proxy for truncated Gaussian and exponential random variables | date=2024 | class=math.ST }}

}}

• {{cite journal

|first1=J.P. |last1=Kahane

|title=Propriétés locales des fonctions à séries de Fourier aléatoires

|journal=Studia Mathematica

|volume=19

|pages=1–25

|year=1960

|doi=10.4064/sm-19-1-1-25 | doi-access=free

}}

• {{Cite book |last=Tao |first=Terence |title=Topics in random matrix theory |date=2012 |publisher=American Mathematical Society |isbn=978-0-8218-7430-1 |series=Graduate studies in mathematics |location=Providence, R.I}}
• {{Cite journal |last=Matoušek |first=Jiří |date=September 2008 |title=On variants of the Johnson–Lindenstrauss lemma |url=https://onlinelibrary.wiley.com/doi/10.1002/rsa.20218 |journal=Random Structures & Algorithms |language=en |volume=33 |issue=2 |pages=142–156 |doi=10.1002/rsa.20218 |issn=1042-9832|url-access=subscription }}
• {{cite journal

|first1=V.V. |last1=Buldygin

|first2=Yu.V. |last2=Kozachenko

|title=Sub-Gaussian random variables

|journal=Ukrainian Mathematical Journal

|volume=32

|pages=483–489

|year=1980

|issue=6

|doi=10.1007/BF01087176 | doi-access=

}}

• {{cite book

| last1 = Ledoux | first1 = Michel

| last2 = Talagrand | first2 = Michel

| title = Probability in Banach Spaces

| year = 1991

| publisher = Springer-Verlag

}}

• {{cite book

| last1 = Stromberg | first1 = K.R.

| title = Probability for Analysts

| year = 1994

| publisher = Chapman & Hall/CRC

}}

• {{cite journal

| first1=A.E. | last1=Litvak

| first2=A. | last2=Pajor

| first3=M. | last3=Rudelson

| first4=N. | last4=Tomczak-Jaegermann

| title=Smallest singular value of random matrices and geometry of random polytopes

| journal=Advances in Mathematics

| volume=195

| pages=491–523

| year=2005

| issue=2

| doi=10.1016/j.aim.2004.08.004 | doi-access=free

| url = http://www.math.ualberta.ca/~alexandr/OrganizedPapers/lprtlastlast.pdf

}}

• {{cite conference

| first1=Mark | last1=Rudelson

| first2=Roman | last2=Vershynin

| title=Non-asymptotic theory of random matrices: extreme singular values

| book-title=Proceedings of the International Congress of Mathematicians 2010

| pages=1576–1602

| arxiv=1003.2990

| doi=10.1142/9789814324359_0111

| year=2010

}}

• {{cite news

| first1=O. | last1=Rivasplata

| title=Subgaussian random variables: An expository note

| journal=Unpublished

| year=2012

| url=http://www.stat.cmu.edu/~arinaldo/36788/subgaussians.pdf

}}

• Vershynin, R. (2018). [https://www.math.uci.edu/~rvershyn/papers/HDP-book/HDP-book.pdf "High-dimensional probability: An introduction with applications in data science"] (PDF). Volume 47 of Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge.
• Zajkowskim, K. (2020). "On norms in some class of exponential type Orlicz spaces of random variables". Positivity. An International Mathematics Journal Devoted to Theory and Applications of Positivity. 24(5): 1231--1240. {{arxiv|1709.02970}}. {{doi|10.1007/s11117-019-00729-6}}.

Category:Continuous distributions