38 Sub-Gaussian random variables
38.1 Prelim: Concentration inequality of sum of Gaussian random variables
Let
Note that if
The tails of Gaussian random variables decay fast which can be quantified using the following inequality.
Proposition 38.1 (Mills inequality) If
More generally, if
We’ll first prove the result for unit variance random variable. Note that
Now, by using an idea similar to the proof of Markov’s inequality, we have
The proof for the general case follows by observing that
The fact that a Gaussian random variable has tails that decay to zero exponentially fast can be be seen in the moment generating function:
A useful application of Mills inequality is the following concentration inequality.
Proposition 38.2 (Concentration inequality.) Let
This follows immediately from Mills inequality and the union bound.
Another useful result is the following:
Proposition 38.3 (Max of Gaussian random variables.) Let
See these notes for a lower bound with the same rate!
We prove the first inequality. The second follows by considering
For any
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).
38.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
Definition 38.1 (Sub-Gaussian random variable) A random variable
The reason the parameter
This definition can be generalized to random vectors and matrices. A random vector
Similarly, a random matrix
We will use the phrase “
38.3 Examples of sub-Gaussian distributions
If
be a Rademacher random variable, i.e., takes the values with probability . Then, so isIf
is uniformly distributed over . Then, for any , Using the inequality , we get that is -sub-Gaussian.It can be shown that (see Rivasplata (2012) ) if
is a random variable with and a.s., then Therefore, is 1-sub-Gaussian.An immediate corollary of the previous example is that if
is a random variable with and a.s., then is -sub-Gaussian. This result is also a consequence of .By a similar arguement, we can show that if
is a zero mean random variable supported on some interval , then is sub-Gaussian.If
is sub-Gaussian, then for any , is -sub-Gaussian.If
and are and -sub-Gaussian, then is -sub-Gaussian.
38.4 Characterization of sub-Gaussian random variables
Sub-Gaussian random variables satisfy a concentration result similar to Mills inequality.
Lemma 38.1 Let
This follows from Chernoff’s bound and the definition of sub-Gaussianity. In particular, for any
Recall that the moments of
Lemma 38.2 Let
Note that for the special case of
This is a simple application of the tail bound.
The result for
Using moments, we can bound the moment generating function in terms of the tail bounds.
Lemma 38.3 Let
For this reason, sometimes it is stated that
The proof follows from the following Taylor series bound on the exponential function.
38.5 Properties of sub-Gaussian random vectors
Theorem 38.1 Let
For any unit vector
38.6 Concentration inequalities
Recall that if
Proposition 38.4 (Hoeffding inequality) Suppose that variables
The Hoeffding inequality is often stated for the special case of bounded random variables. In particular, if
The Hoeffding inequality can be generalized to Martingales. See Theorem 42.6.
38.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 38.2 Let
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 38.3 Let
Maximum over the ball
Theorem 38.4 Let
For any
38.8 Lipschitz functions of Gaussian variables.
Recall that a function
The following results shows that any Lipschitz function of a Gaussian random variable is
Theorem 38.5 Let
This result is remarkable because it guarantees that any
For a proof, see Chapter 2 of Wainwright (2019).