39  Sub-Gaussian random variables

Author

Affiliation

Aditya Mahajan

McGill University

39.1 Prelim: Concentration inequality of sum of Gaussian random variables

Let $\varphi (\cdot )$ denote the density of $\mathcal{N}(0,1)$ Gaussian random variable: $$\varphi (x)=\frac{1}{\sqrt{2\pi }}\exp (-\frac{x^2}{2}).$$

Note that if $X\sim \mathcal{N}(\mu ,{\sigma }^2)$, then the density of $X$ is $$\frac{1}{\sigma }\varphi (\frac{x-\mu }{\sigma })=\frac{1}{\sqrt{2\pi }\sigma }\exp (-\frac{(x-\mu {)}^2}{2{\sigma }^2}).$$

The tails of Gaussian random variables decay fast which can be quantified using the following inequality.

Proposition 39.1 (Mills inequality) If $X\sim \mathcal{N}(0,1)$, then for any $t>0$, $$\mathbb{P}(|X|>t)\le \frac{2\varphi (t)}{t}$$

More generally, if $X\sim \mathcal{N}(0,{\sigma }^2)$, then for any $t>0$, $$\mathbb{P}(|X|>t)\le 2\frac{\sigma }{t}\varphi (\frac{t}{\sigma })=\sqrt{\frac{2}{\pi }}\frac{\sigma }{t}\exp (-\frac{t^2}{2{\sigma }^2}).$$

Remark

In the communication theory literature, this bound is sometimes known as the bound on the erfc or $Q$ function.

Proof

We’ll first prove the result for unit variance random variable. Note that $X$ is symmetric around origin. Therefore, $$\mathbb{P}(|X|>t)=2\mathbb{P}(X>t).$$

Now, by using an idea similar to the proof of Markov’s inequality, we have $$\begin{array}{rl}t\cdot \mathbb{P}(|X|>t)& =t{\int }_t^{\infty }\varphi (x)dx\\ & \le {\int }_t^{\infty }x\varphi (x)dx\\ & ={\int }_t^{\infty }\frac{1}{\sqrt{2\pi }}x\exp (-\frac{x^2}{2})dx\\ & =\frac{1}{\sqrt{2\pi }}{\int }_t^{\infty }-\frac{\partial }{\partial x}\exp (-\frac{x^2}{2})dx\\ & =\frac{1}{\sqrt{2\pi }}\exp (-\frac{t^2}{2})\end{array}$$

The proof for the general case follows by observing that $$\mathbb{P}(|X|>t)=\mathbb{P}(|\frac{X}{\sigma }|>\frac{t}{\sigma })$$ where $X/\sigma \sim \mathcal{N}(0,1)$.

The fact that a Gaussian random variable has tails that decay to zero exponentially fast can be be seen in the moment generating function: $$M(s)=\mathbb{E}[\exp (sX)]=\exp (s\mu +\frac{1}{2}{s}^2{\sigma }^2).$$

A useful application of Mills inequality is the following concentration inequality.

Proposition 39.2 (Concentration inequality.) Let $X_i\sim \mathcal{N}(0,{\sigma }^2)$ (not necessarily independent). Then, for any $t>0$, $$\mathbb{P}(\underset{1\le i\le n}{max}|X_i|>t)\le 2n\frac{\sigma }{t}\varphi (\frac{t}{\sigma }).$$

Proof

This follows immediately from Mills inequality and the union bound.

Another useful result is the following:

Proposition 39.3 (Max of Gaussian random variables.) Let $X_i\sim \mathcal{N}(0,{\sigma }^2)$ (not necessarily independent). Then, $$\mathbb{E}[\underset{1\le i\le n}{max}{X}_i]\le \sigma \sqrt{2\log n}$$ and $$\mathbb{E}[\underset{1\le i\le n}{max}|X_i|]\le \sigma \sqrt{2\log 2n}.$$

See these notes for a lower bound with the same rate!

Proof

We prove the first inequality. The second follows by considering $2n$ random variables $X_1,\dots ,X_n$, $-X_1,\dots ,-X_n$.

For any $s>0$, $$\begin{array}{rl}\mathbb{E}[\underset{1\le i\le n}{max}{X}_i]& =\frac{1}{s}\mathbb{E}[\log (\exp (s\underset{1\le i\le n}{max}{X}_i))]\\ & \stackrel{(a)}{\le }\frac{1}{s}\log (\mathbb{E}[\exp (s\underset{1\le i\le n}{max}{X}_i)])\\ & \stackrel{(b)}{=}\frac{1}{s}\log (\mathbb{E}[\underset{1\le i\le n}{max}\exp (s{X}_i)])\\ & \stackrel{(c)}{\le }\frac{1}{s}\log (\sum _{i=1}^n\mathbb{E}[\exp (s{X}_i)])\\ & \stackrel{(d)}{=}\log (\sum _{i=1}^n\exp (\frac{s^2{\sigma }^2}{2}))\\ & =\frac{\log n}{s}+\frac{s^2{\sigma }^2}{2}\end{array}$$ where $(a)$ follows from Jensen’s inequality, $(b)$ follows from monotonicity of $\exp (\cdot )$, $(c)$ follows from definition of max, $(d)$ follows from the definition of moment generating function of Gaussian random variables. We get the result by setting $s=\sqrt{2\log n}/\sigma$ (which minimizes the upper bound).

Remark

We have stated and proved these inequalities for real-valued random variables. But a version of them continue to hold for vector valued Gaussian variables as well. For a complete treatment, see Picard (2007).

39.2 Sub-Gaussian random variables

It turns out that the concentration inequalities of the form above continue to hold for more general distributions than the Gaussian. In particular, consider the bound on the max of Gaussian random variables that we established above. The only step which depends on the assumption that the random variables $X_i$ were Gaussian in step $(d)$. Thus, as long as $\mathbb{E}[\exp (s{X}_i)]\le \exp (\frac{1}{2}{s}^2{\sigma }^2)$, the result will continue to hold! This motivates the definition of sub-Gaussian random variables.

Definition 39.1 (Sub-Gaussian random variable) A random variable $X\in \mathbb{R}$ is said to be sub-Gaussian with variance proxy ${\sigma }^2$ if $\mathbb{E}[X]=0$ and its moment generating function satisfies $$\mathbb{E}[\exp (sX)]\le \exp (\frac{1}{2}{s}^2{\sigma }^2),\mathrm{\forall }s\in \mathbb{R}.$$

The reason the parameter ${\sigma }^2$ is called a variance proxy is because by a straight forward application of Taylor series expansion and comparing coefficients, it can be shown that $\text{var}(X)\le {\sigma }^2$. See Rivasplata (2012) for a proof.

This definition can be generalized to random vectors and matrices. A random vector $X\in {\mathbb{R}}^d$ is said the be sub-Gaussian with variance proxy ${\sigma }^2$ if $\mathbb{E}[X]=0$ and for any unit vector $u\in {\mathbb{R}}^d$, $u^{⊺}X$ is sub-Gaussian with variance proxy ${\sigma }^2$.

Similarly, a random matrix $X\in {\mathbb{R}}^{d_1\times d_2}$ is said to be sub-Gaussian with variance proxy ${\sigma }^2$ if $\mathbb{E}[X]=0$ and for any unit vectors $u\in {\mathbb{R}}^{d_1}$ and $v\in {\mathbb{R}}^{d_2}$, $u^{⊺}Xv$ is sub-Gaussian with variance proxy ${\sigma }^2$.

We will use the phrase “$\sigma$-sub-Gaussian” as a short form of “sub-Gaussian with variance proxy ${\sigma }^2$”. One typically writes $X\sim \text{subG}({\sigma }^2)$ to denote a random variable with sub-Gaussian distribution with variance proxy ${\sigma }^2$. (Strictly speaking, this notation is a bit ambiguous since $\text{subG}({\sigma }^2)$ is a class of distributions rather than a single distribution.)

39.3 Examples of sub-Gaussian distributions

1. If $X$ be a Rademacher random variable, i.e., $X$ takes the values $\pm 1$ with probability $1/2$. Then, $$\mathbb{E}[\exp (sX)]=\frac{1}{2}{e}^{-s}+\frac{1}{2}{e}^s=\cosh s\le \exp (\frac{1}{2}{s}^2),$$ so $X$ is

2. If $X$ is uniformly distributed over $[-a,a]$. Then, for any $s\ne 0$, $$\mathbb{E}[\exp (sX)]=\frac{1}{2as}[e^{as}-e^{-as}]=\sum _{n=0}^{\infty }\frac{(as{)}^{2n}}{(2n+1)!}.$$ Using the inequality $(2n+1)!\ge n!2^n$, we get that $X$ is $a$-sub-Gaussian.

3. It can be shown that (see Rivasplata (2012) ) if $X$ is a random variable with $\mathbb{E}[X]=0$ and $|X|<1$ a.s., then $$\mathbb{E}[\exp (sX)]\le \cosh s,\mathrm{\forall }s\in \mathbb{R}.$$ Therefore, $X$ is 1-sub-Gaussian.

4. An immediate corollary of the previous example is that if $X$ is a random variable with $\mathbb{E}[X]=0$ and $|X|\le b$ a.s., then $X$ is $b$-sub-Gaussian. This result is also a consequence of Hoeffding’s Lemma.

5. By a similar arguement, we can show that if $X$ is a zero mean random variable supported on some interval $[a,b]$, then $X$ is $(b-a)/2$ sub-Gaussian.

6. If $X$ is ${\sigma }^2$ sub-Gaussian, then for any $\alpha \in \mathbb{R}$, $\alpha X$ is $|\alpha |\sigma$-sub-Gaussian.

7. If $X_1$ and $X_2$ are ${\sigma }_1$ and ${\sigma }_2$-sub-Gaussian, then $X_1+X_2$ is $\sqrt{{\sigma }_1^2+{\sigma }_2^2}$-sub-Gaussian.

39.4 Characterization of sub-Gaussian random variables

Sub-Gaussian random variables satisfy a concentration result similar to Mills inequality.

Lemma 39.1 Let $X\in \mathbb{R}$ be $\sigma$-sub-Gaussian. Then, for any $t>0$, $$\begin{array}{}\text{(1)}& \mathbb{P}(X>t)\le \exp (-\frac{t^2}{2{\sigma }^2})\text{and}\mathbb{P}(X<-t)\le \exp (-\frac{t^2}{2{\sigma }^2})\end{array}$$

Proof

This follows from Chernoff’s bound and the definition of sub-Gaussianity. In particular, for any $s>0$ $$\mathbb{P}(X>t)=\mathbb{P}(\exp (sX)>\exp (st))\le \frac{\mathbb{E}[\exp (sX)]}{\exp (st)}\le \exp (\frac{s^2{\sigma }^2}{2}-st).$$ Now, to find the tightest possible bound, we minimize the above bound with respect to $s$, which is attained at $s=t/{\sigma }^2$. Substituting this in the above bound, we get the first inequality. The second inequality follows from a similar argument.

Recall that the moments of $Z\sim \mathcal{N}(0,{\sigma }^2)$ are given by $$\mathbb{E}[|Z{|}^k]=\frac{1}{\sqrt{\pi }}(2{\sigma }^2{)}^{k/2}\mathrm{\Gamma }(\frac{k+1}{2}),$$ where $\mathrm{\Gamma }(\cdot )$ denotes the Gamma function. The next result shows that the tail bounds $\text{(1)}$ are sufficient to show that the absolute moments of $X\sim \text{subG}({\sigma }^2)$ can be bounded by those of $Z\sim \mathcal{N}(0,{\sigma }^2)$ up to multiplicative constants.

Lemma 39.2 Let $X$ be a random variable such that $$\mathbb{P}(|X|>t)\le 2\exp (-\frac{t^2}{2{\sigma }^2}),$$ then for any positive integer $k\ge 1$, $$\mathbb{E}[|X{|}^k]\le (2{\sigma }^2{)}^{k/2}k\mathrm{\Gamma }(k/2).$$

Note that for the special case of $k=1$, the above bound implies $\mathbb{E}[|X|]\le \sigma \sqrt{2\pi }$ and for $k=2$, $\mathbb{E}[|X{|}^2]\le 4{\sigma }^2$.

Proof

This is a simple application of the tail bound. $$\begin{array}{rl}\mathbb{E}[|X{|}^k]& ={\int }_0^{\infty }\mathbb{P}(|X{|}^k>t)dt\\ & ={\int }_0^{\infty }\mathbb{P}(|X|>t^{1/k})dt\\ & \le 2{\int }_0^{\infty }\exp (-\frac{t^{2/k}}{2{\sigma }^2})dt\\ & =(2{\sigma }^2{)}^{k/2}k{\int }_0^{\infty }{e}^{-u}{u}^{k/2-1}du,u=\frac{t^{2/k}}{2{\sigma }^2}\\ & =(2{\sigma }^2{)}^{k/2}k\mathrm{\Gamma }(k/2).\end{array}$$

The result for $k=1$ follows from $\mathrm{\Gamma }(1/2)=\sqrt{\pi /2}$.

Using moments, we can bound the moment generating function in terms of the tail bounds.

Lemma 39.3 Let $X$ be a random variable such that $$\mathbb{P}(|X|>t)\le 2\exp (-\frac{t^2}{2{\sigma }^2})$$ then, $$\mathbb{E}[\exp (sX)]\le \exp (4s^2{\sigma }^2).$$

For this reason, sometimes it is stated that $X\sim \text{subG}({\sigma }^2)$ when it satisfies the tail bound $\text{(1)}$.

Proof

The proof follows from the following Taylor series bound on the exponential function. $$\exp (sX)\le 1+\sum _{k=2}^{\infty }\frac{s|X{|}^k}{k!}$$ and apply the result of Lemma 39.2. See Rigollet (2015) for details.

39.5 Properties of sub-Gaussian random vectors

Theorem 39.1 Let $X=(X_1,\dots ,X_n)$ be a vector of independent $\sigma$-sub-Gaussian random variables. Then, the random vector $X$ is $\sigma$-sub-Gaussian.

Proof

For any unit vector $u\in {\mathbb{R}}^n$, and any $s\in \mathbb{R}$ $$\begin{array}{rl}\mathbb{E}[\exp (s{u}^{⊺}X)]& =\prod _{i=1}^n\mathbb{E}[\exp (s{u}_i{X}_i)]\\ & \le \prod _{i=1}^n\exp (\frac{1}{2}{s}^2{u}_i^2{\sigma }^2)\\ & =\exp (\frac{1}{2}{s}^2\parallel u{\parallel }^2{\sigma }^2)\\ & =\exp (\frac{1}{2}{s}^2{\sigma }^2).\end{array}$$

39.6 Concentration inequalities

Recall that if $X_1$ and $X_2$ and ${\sigma }_1$ and ${\sigma }_2$-sub-Gaussian, then $X_1+X_2$ is sub-Gaussian with variance proxy ${\sigma }_1^2+{\sigma }_2^2$. An immediate implication of this property is the following:

Proposition 39.4 (Hoeffding inequality) Suppose that variables $X_i$, $i\in \{1,\dots ,n\}$, are independent and $X_i$ has mean ${\mu }_i$ and ${\sigma }_i$-sub-Gaussian. Then, for all $t>0$, we have

$$\mathbb{P}(\sum _{i=1}^n(X_i-{\mu }_i)\ge t)\le \exp (-\frac{t^2}{2\sum _{i=1}^n{\sigma }_i^2}).$$

The Hoeffding inequality is often stated for the special case of bounded random variables. In particular, if $X_i\in [a,b]$, then we know that $X_i$ is sub-Gaussian with parameter $\sigma =(b-a)/2$, so we obtain the bound $$\mathbb{P}(\sum _{i=1}^n(X_i-{\mu }_i)\ge t)\le \exp (-\frac{2t^2}{\sum _{i=1}^{n}n(b-a{)}^2}).$$

The Hoeffding inequality can be generalized to Martingales. See Theorem 43.6.

39.7 Maximal inequalities

As we explained in the motivation for the definition of sub-Gaussian random variables, the definition implies that sub-Gaussian random variables will satisfy the concentration and maximal inequalities for Gaussian random variables. In particular, we have the following general result.

Theorem 39.2 Let $X_i\in \mathbb{R}$ be $\sigma$-sub-Gaussian random variables (not necessarily independent). Then, $$\mathbb{E}[\underset{1\le i\le n}{max}{X}_i]\le \sigma \sqrt{2\log n}\text{and}\mathbb{E}[\underset{1\le i\le n}{max}|X_i|]\le \sigma \sqrt{2\log 2n}.$$ Moreover, for any $t>0$, $$\mathbb{P}(\underset{1\le i\le n}{max}{X}_i>t)\le n\exp (-\frac{t^2}{2{\sigma }^2})\text{and}\mathbb{P}(\underset{1\le i\le n}{max}|X_i|>t)\le 2n\exp (-\frac{t^2}{2{\sigma }^2}).$$

The proof is exactly the same as the Gaussian case!

Now we state two generalizations without proof. See Rigollet (2015) for proof.

Maximum over a convex polytope

Theorem 39.3 Let $\mathsf{P}$ be a polytope with $n$ vertices $v^{(1)},\dots ,v^{(n)}\in {\mathbb{R}}^d$ and let $X\in {\mathbb{R}}^d$ be a random variable such that $[v^{(i)}{]}^{⊺}X$, $i\in \{1,\dots ,n\}$ are $\sigma$-sub-Gaussian random variables. Then, $$\mathbb{E}[\underset{\theta \in \mathsf{P}}{max}{\theta }^{⊺}X]\le \sigma \sqrt{2\log n}\text{and}\mathbb{E}[\underset{\theta \in \mathsf{P}}{max}|{\theta }^{⊺}X|]\le \sigma \sqrt{2\log 2n}.$$ Moreover, for any $t>0$, $$\mathbb{P}(\underset{\theta \in \mathsf{P}}{max}{\theta }^{⊺}X>t)\le n\exp (-\frac{t^2}{2{\sigma }^2})\text{and}\mathbb{P}(\underset{\theta \in \mathsf{P}}{max}|{\theta }^{⊺}X|>t)\le 2n\exp (-\frac{t^2}{2{\sigma }^2}).$$

Maximum over the ${\ell }_2$ ball

Theorem 39.4 Let $X\in {\mathbb{R}}^d$ be a $\sigma$-sub-Gaussian random variable. Then, $$\mathbb{E}[\underset{\parallel \theta \parallel \le 1}{max}{\theta }^{⊺}X]=\mathbb{E}[\underset{\parallel \theta \parallel \le 1}{max}|{\theta }^{⊺}X|]\le 4\sigma \sqrt{d}.$$ Moreover, for any $t>0$ $$\mathbb{P}(\underset{\parallel \theta \parallel \le 1}{max}{\theta }^{⊺}X>t)=\mathbb{P}(\underset{\parallel \theta \parallel \le 1}{max}|{\theta }^{⊺}X|>t)\le 6^d\exp (-\frac{t^2}{8{\sigma }^2}).$$

Remark

For any $\delta >0$, take $t=\sigma \sqrt{8d\log 6}+2\sigma \sqrt{2\log (1/\delta )}$, we obtain that with probability less than $1-\delta$, it holds that $$\underset{\parallel \theta \parallel \le 1}{max}{\theta }^{⊺}X=\underset{\parallel \theta \parallel \le 1}{max}|{\theta }^{⊺}X|\le 4\sigma \sqrt{d}+2\sigma \sqrt{2\log (1/\delta )}.$$

39.8 Lipschitz functions of Gaussian variables.

Recall that a function $f:{\mathbb{R}}^d\to \mathbb{R}$ is $L$-Lipschitz with respect to the Eucledian norm if $$|f(x)-f(y)|\le L\parallel x-y{\parallel }_2,\mathrm{\forall }x,y\in {\mathbb{R}}^d.$$

The following results shows that any Lipschitz function of a Gaussian random variable is $L$-sub-Gaussian.

Theorem 39.5 Let $X=(X_1,\dots ,X_n)$ be a vector of i.i.d. standard Gaussian random variables and let $f:{\mathbb{R}}^n\to \mathbb{R}$ be $L$-Lipschitz with respect to the Euclidean norm. Then, the variable $f(X)-\mathbb{E}[f(X)]$ is $L$-sub-Gaussian and therefore $$\mathbb{P}[|f(X)-\mathbb{E}[f(X)]|\ge t]\le 2\exp (-\frac{t^2}{2L^2}).$$

This result is remarkable because it guarantees that any $L$-Lipschitz function of a standard Gaussian random vector, irrespective of the dimension, exhibits concetration like a scalar Gaussian variable with variance $L^2$.

For a proof, see Chapter 2 of Wainwright (2019).

Picard, J. 2007. Concentration inequalities and model selection. Springer Berlin Heidelberg. DOI: 10.1007/978-3-540-48503-2.

Rigollet, P. 2015. High-dimensional statistics. Available at: https://ocw.mit.edu/courses/mathematics/18-s997-high-dimensional-statistics-spring-2015/lecture-notes/.

Rivasplata, O. 2012. Subgaussian random variables: An expository note. Available at: http://stat.cmu.edu/~arinaldo/36788/subgaussians.pdf.

Wainwright, M.J. 2019. High-dimensional statistics. Cambridge University Press. DOI: 10.1017/9781108627771.