STT 996 – High-Dimensional Probability
Lecture L04
Monday, January 26, 2026
Subexponential Distribution (Sub-Ex)
Proposition
Let $ X $ be a real-valued random variable.
Then the following are equivalent (up to constants $ k_1, k_2, k_3 $):
-
Tail bound \(\mathbb{P}(|X| > t) \le 2 e^{-t/k_1}, \quad t > 0\)
-
Moment growth \(\|X\|_p \le k_2 \, p, \quad p \ge 1\)
-
Exponential moment \(\mathbb{E}\!\left(e^{|X|/k_3}\right) \le 2\)
-
Centered version If $ \mathbb{E}[X] = 0 $, then (1), (2), (3) are equivalent to: \(\mathbb{E}(e^{\lambda X}) \le e^{k_4^2 \lambda^2}, \quad |\lambda| \le \frac{1}{k_4}\)
Why do we drop (2) ⇔ (3)?
Because sub-Gaussian squared is sub-exponential.
Proof Sketch: (2) ⇒ (4)
Using the power series expansion: \(\mathbb{E}(e^{\lambda X}) = \mathbb{E}\left(1 + \lambda X + \sum_{p \ge 2} \frac{(\lambda X)^p}{p!}\right)\)
Since $ \mathbb{E}[X] = 0 $, \(= 1 + \sum_{p \ge 2} \frac{\lambda^p \mathbb{E}(X^p)}{p!}\)
Using (2): \(|\mathbb{E}(X^p)| \le \|X\|_p^p \le (k p)^p\)
Hence, \(\le 1 + \sum_{p \ge 2} \frac{(\lambda k p)^p}{p!}\)
Using Stirling’s approximation: \(\frac{p^p}{p!} \le \frac{e^p}{\sqrt{p}}\)
Thus, \(\sum_{p \ge 2} (\lambda k e)^p\)
If $ |\lambda| < \frac{1}{2ke} $, geometric series gives: \(\le 1 + 2(\lambda k e)^2 \le e^{C \lambda^2 k^2}\)
Facts
-
Sub-Gaussian norm \(\|X\|_{\psi_2}^2 = \|X^2\|_{\psi_1}\)
-
Product of sub-Gaussians If $ X, Y $ are sub-Gaussian r.v.s, then \(XY \text{ is sub-Ex}, \quad \|XY\|_{\psi_1} \le \|X\|_{\psi_2}\|Y\|_{\psi_2}\)
WLOG: $ |X|{\psi_2} = |Y|{\psi_2} = 1 $
Using: \(x^2 y^2 \le \frac{x^4}{2} + \frac{y^4}{2}\)
and tensorization, \(\mathbb{E}(e^{X^2 Y^2}) \le 2\)
Orlicz Norms
Recall
A function $ \Psi : \mathbb{R}^+ \to \mathbb{R}^+ $ satisfies:
- $ \Psi(0) = 0 $
- $ \Psi $ increasing
- $ \Psi $ convex
- $ \lim_{x \to \infty} \Psi(x) = \infty $
Orlicz Function
\(\Psi(x) = e^x - 1\)
Orlicz Norm
\(\|X\|_\Psi = \inf\left\{ k > 0 : \mathbb{E}\left[\Psi\left(\frac{|X|}{k}\right)\right] \le 1 \right\}\)
Properties
-
Triangle inequality \(\|X + Y\|_\Psi \le \|X\|_\Psi + \|Y\|_\Psi\)
-
Homogeneity \(\|aX\|_\Psi = |a| \|X\|_\Psi\)
Proof idea:
Use convexity of $ \Psi $ and Jensen’s inequality.
Bernstein Concentration Inequality
Theorem
Let $ X_1, \dots, X_n $ be independent, mean-zero, sub-Ex random variables.
Then:
$$
\mathbb{P}!\left(
\left|\sum_{k=1}^n X_k\right| \ge t
\right)
\le
2 \exp\left[
- c \min\left( \frac{t^2}{\sum_k |X_k|{\psi_1}^2}, \frac{t}{\max_k |X_k|{\psi_1}} \right) \right] $$
Weighted Version
For coefficients $ a_k $: $$ \mathbb{P}!\left( \left|\sum_{k=1}^n a_k X_k\right| \ge t \right) \le 2 \exp\left[
- c \min\left( \frac{t^2}{\sum_k a_k^2 |X_k|{\psi_1}^2}, \frac{t}{\max_k |a_k| |X_k|{\psi_1}} \right) \right] $$
Special case: $$ a_k = \frac{1}{n} \quad \Rightarrow \quad \mathbb{P}(|\bar X| > t) \le 2 \exp\left[
- c n \min\left(\frac{t^2}{K^2}, \frac{t}{K}\right) \right] $$
Proof Sketch (MGF Method)
Let: \(S_n = \sum_{k=1}^n X_k\)
Then: \(\mathbb{P}(S_n > t) \le e^{-\lambda t} \mathbb{E}(e^{\lambda S_n}) = e^{-\lambda t} \prod_{k=1}^n \mathbb{E}(e^{\lambda X_k})\)
Using sub-Ex MGF bound: \(\mathbb{E}(e^{\lambda X_k}) \le e^{C \lambda^2 \|X_k\|_{\psi_1}^2}\)
Thus: \(\le \exp\left( -\lambda t + C \lambda^2 \sum_k \|X_k\|_{\psi_1}^2 \right)\)
Optimize: \(\lambda^* = \frac{t}{2C \sum_k \|X_k\|_{\psi_1}^2}\)
Geometric Example
Let: \(Z = (Z_1, \dots, Z_n), \quad Z_k \stackrel{iid}{\sim} \mathcal{N}(0,1)\)
Define the sphere: \(S^{n-1} = \{ x \in \mathbb{R}^n : \|x\|_2 = 1 \}\)
Then: \(\frac{Z}{\|Z\|_2} \sim \text{Uniform}(S^{n-1})\)
Intro to Chapter 3
Comments