Sub-Gaussian distribution

A real centered random variable $X$ is sub-Gaussian random variable with parameter $\sigma \ge 0$ if its moment-generating function satisfiesThe parameter is an upper bound on fluctuation size, not necessarily the standard deviation. For $\sigma >0$ and $u>0$, exponential Markov inequality gives $\mathbb{P}(X\ge u)\le \exp (-tu+{\sigma }^2{t}^2/2)$. Choosing $t=u/{\sigma }^2$ and applying the same argument to $-X$ yields the Chernoff boundA centered normal distribution of variance ${\sigma }^2$ attains equality in the moment-generating-function condition. A Rademacher distribution also satisfies it with $\sigma =1$, since $\cosh t\le e^{t^2/2}$. Products of moment-generating functions show that a sum of independent centered sub-Gaussian random variables with parameters ${\sigma }_i$ is sub-Gaussian with parameter $({\sum }_i{\sigma }_i^2{)}^{1/2}$. Hence the sample mean of $n$ independent variables with a common parameter $\sigma$ has tail bound $2e^{-n{u}^2/(2{\sigma }^2)}$. This gives normal-like concentration without assuming a normal distribution. For an uncentered variable, the convention is to apply the condition to $X-\mathbb{E}X$.

A sub-Gaussian deviation bound controls tails through a Gaussian-shaped exponential. If a centered random variable $X$ satisfies $\mathbb{E}{e}^{tX}\le e^{{\sigma }^2{t}^2/2}$ for every real $t$, with $\sigma >0$, then for $u>0$,Indeed, exponential Markov's inequality gives $\mathbb{P}(X\ge u)\le \exp (-tu+{\sigma }^2{t}^2/2)$; minimizing at $t=u/{\sigma }^2$ and applying the argument to $-X$ proves the result.

Independent centered observations with a common variance proxy ${\sigma }^2$ therefore satisfy $\mathbb{P}(|\overline{X}|\ge u)\le 2e^{-n{u}^2/(2{\sigma }^2)}$. The proxy need not equal the actual variance, and dependence requires a separate argument rather than automatic multiplication of moment-generating functions.

A centered random vector is sub-Gaussian with variance proxy ${\tau }^2$ when the displayed inequality holds for every deterministic vector $a$. Equivalently every scalar inner product is a sub-Gaussian random variable with proxy ${\tau }^2\Vert a{\Vert }_2^2$. independence of coordinates is not required. For vectors $a_j$ with Euclidean norms at most one, the union bound gives ${\max }_j|⟨a_j,g⟩|\le \tau \sqrt{2\log (2m/\delta )}$ with probability at least $1-\delta$. This assumption alone is weaker than concentration for all Lipschitz functions.