Sub-Gaussian and Sub-Exponential Random Variables

Orlicz norms, moment generating functions and the equivalent characterisations that make "has a Gaussian-like tail" a usable hypothesis.

High-Dim ProbabilityAdvanced⏱ 3 hours15 min readsub-gaussiansub-exponentialorlicz normmgftails

5 problems →

AssumesModes of Convergence, LLN and CLT · Analysis Prerequisites

Definition through four equivalent lenses

TheoremEquivalent characterisations of sub-Gaussianity

Let $X$ be a random variable. The following are equivalent, in the sense that if one holds with parameter $K_i$ then the others hold with parameters $K_j \le C K_i$ for an absolute constant $C$ :

Tails. $\P(|X| \ge t) \le 2\exp(-t^2/K_1^2)$ for all $t \ge 0$ .
Moments. $\norm{X}_{L^p} = (\E|X|^p)^{1/p} \le K_2\sqrt p$ for all $p \ge 1$ .
MGF of the square. $\E\exp(X^2/K_3^2) \le 2$ .
MGF (centred case). If in addition $\E X = 0$ , then $\E\exp(\lambda X) \le \exp(\lambda^2 K_4^2)$ for all $\lambda \in \R$ .

The Orlicz norms

DefinitionThe psi-2 and psi-1 Orlicz norms

\norm{X}_{\psi_2} = \inf\left\{ t > 0 : \E\exp\!\left(\frac{X^2}{t^2}\right) \le 2 \right\}, \qquad \norm{X}_{\psi_1} = \inf\left\{ t>0 : \E\exp\!\left(\frac{|X|}{t}\right) \le 2\right\}.

$X$ is sub-Gaussian if $\norm{X}_{\psi_2} < \infty$ and sub-exponential if $\norm{X}_{\psi_1} < \infty$ .

These are genuine norms — positivity, homogeneity and the triangle inequality all hold — which is what makes them so convenient: one can manipulate $\norm{\cdot}_{\psi_2}$ with the same reflexes as $\norm{\cdot}_{L^2}$ . The choice of the constant $2$ on the right-hand side is a convention; any constant $>1$ gives an equivalent norm.

LemmaMoment generating function of a centred Gaussian

If $X \sim \Ncal(0,\sigma^2)$ then $\E e^{\lambda X} = e^{\lambda^2\sigma^2/2}$ for every $\lambda\in\R$ .

This identity is the template: a centred variable is called sub-Gaussian with parameter $\sigma$ when $\E e^{\lambda X} \le e^{\lambda^2\sigma^2/2}$ for all $\lambda$ , i.e. when its MGF is dominated by that of a Gaussian of that variance. Note that a sub-Gaussian variable with parameter $\sigma$ automatically has $\Var(X) \le \sigma^2$ , by comparing second-order Taylor coefficients at $\lambda = 0$ — but the converse fails badly, and "sub-Gaussian with parameter $\sigma$ " is a strictly stronger statement than "variance $\sigma^2$ ".

Bounded variables are sub-Gaussian

LemmaHoeffding's lemma

Let $X$ satisfy $\E X = 0$ and $X \in [a,b]$ almost surely. Then for all $\lambda \in \R$ ,

\E e^{\lambda X} \le \exp\!\left(\frac{\lambda^2(b-a)^2}{8}\right),

i.e. $X$ is sub-Gaussian with parameter $(b-a)/2$ .

Key idea

The variance-of-the-tilted-measure computation is the whole proof. It is worth internalising because the same three steps — cumulant generating function, tilted measure, bound the variance uniformly — prove Bernstein's inequality, the Azuma–Hoeffding inequality and the log-Sobolev route to Gaussian concentration. The tilting is not a trick; it is the natural coordinate system for exponential tail bounds.

Sums, and why parameters add in square

PropositionSums of independent sub-Gaussians

Let $X_1,\dots,X_n$ be independent, centred, with $X_i$ sub-Gaussian of parameter $\sigma_i$ . Then $S = \sum_i X_i$ is sub-Gaussian with parameter $\big(\sum_i \sigma_i^2\big)^{1/2}$ . Equivalently, in Orlicz form,

\norm{\sum_i X_i}_{\psi_2}^2 \le C\sum_i \norm{X_i}_{\psi_2}^2 .

Sub-exponential variables

Sub-Gaussianity is sometimes too much to ask. The square of a Gaussian, the product of two Gaussians, and an exponential random variable all have tails that decay like $e^{-ct}$ rather than $e^{-ct^2}$ — and that is the next class down.

TheoremEquivalent characterisations of sub-exponentiality

The following are equivalent up to absolute constants:

$\P(|X| \ge t) \le 2e^{-t/K_1}$ for all $t \ge 0$ ;
$\norm{X}_{L^p} \le K_2\,p$ for all $p \ge 1$ ;
$\E e^{|X|/K_3} \le 2$ ;
if $\E X = 0$ : $\E e^{\lambda X} \le e^{\lambda^2K_4^2}$ for all $|\lambda| \le 1/K_4$ .

LemmaThe square of a sub-Gaussian variable is sub-exponential

$\norm{X^2}_{\psi_1} = \norm{X}_{\psi_2}^2$ .

Key idea

This identity is why sub-exponential variables cannot be avoided even in a purely Gaussian world. The squared norm $\norm{X}_2^2 = \sum_i X_i^2$ of a Gaussian vector is a sum of sub-exponential terms, not sub-Gaussian ones, so the concentration of the norm on the next page must be proved with Bernstein's inequality rather than Hoeffding's. The same is true of every covariance estimate, since covariance entries are products of coordinates.

Problems

The psi-2 norm of a GaussianNumerical · Intermediate · 15 min The psi-2 norm of a Rademacher signNumerical · Beginner · 15 min From moment growth to a tail boundProof · Advanced · 1 hour A variable with all moments finite that is not sub-GaussianProof · Intermediate · 30 min Products of sub-Gaussians are sub-exponentialProof · Advanced · 30 min

References

BookRoman Vershynin (2018). High-Dimensional Probability: An Introduction with Applications in Data ScienceChapter 2 is the canonical modern treatment of this material. The exposition below is written independently; the reader who wants the fully general statements, with all constants tracked, should go there.
BookStéphane Boucheron, Gábor Lugosi and Pascal Massart (2013). Concentration Inequalities: A Nonasymptotic Theory of IndependenceChapter 2 develops the same material through the entropy method.
BookMartin J. Wainwright (2019). High-Dimensional Statistics: A Non-Asymptotic ViewpointChapter 2, with an emphasis on the statistical consequences.

These works are cited as sources to read, not reproduced. All exposition, examples and problems on this site are written independently; where an argument is standard, the citation points to a canonical treatment.

Results stated on this page

TheoremEquivalent characterisations of sub-Gaussianityproof includedGaussian tails, moment growth, MGF bounds and finiteness of the psi-2 Orlicz norm are equivalent up to absolute constants.
DefinitionThe psi-2 and psi-1 Orlicz normsNorms whose finiteness encodes Gaussian and exponential tail decay respectively.
LemmaMoment generating function of a centred Gaussianproof includedA centred Gaussian has MGF exactly exp(lambda^2 sigma^2 / 2).
LemmaHoeffding's lemmaproof includedA centred random variable supported on an interval of length b-a is sub-Gaussian with parameter (b-a)/2.
PropositionSums of independent sub-Gaussians are sub-Gaussianproof includedSub-Gaussian parameters add in square, exactly as variances do.
TheoremEquivalent characterisations of sub-exponentialityproof includedExponential tails, linear moment growth and a one-sided MGF bound near zero are equivalent up to constants.
LemmaThe square of a sub-Gaussian variable is sub-exponentialproof includedX sub-Gaussian implies X^2 sub-exponential, with the psi-1 norm the square of the psi-2 norm.

Problems (5)

All problems