Edit this page on GitHub

STT 996 – High Dimensional Probability

Lecture 03 – Sub-Gaussian and Sub-Exponential Variables

Wednesday, January 21, 2026

1. Review: Equivalent Definitions of Sub-Gaussian RVs

Let $ X $ be a real-valued random variable.

There exist absolute constants $ c, k_1, k_2, k_3, k_4 > 0 $ such that \(\frac{1}{c} \le \frac{k_i}{k_j} \le c \quad \text{for all } i,j,\) and the following are equivalent:

TFAE (The Following Are Equivalent)

  1. Tail bound \(\mathbb{P}(|X| > t) \le 2 e^{-t^2/k_1^2}, \quad t > 0\)

  2. Moment growth \(\|X\|_{L^p} := (\mathbb{E}|X|^p)^{1/p} \le k_2 \sqrt{p}, \quad p \ge 1\)

  3. Exponential square integrability \(\mathbb{E}\left[e^{X^2/k_3^2}\right] \le 2\)

If additionally $ \mathbb{E}[X] = 0 $, then these are also equivalent to:

  1. MGF bound \(\mathbb{E}[e^{\lambda X}] \le e^{k_4^2 \lambda^2}, \quad \lambda \in \mathbb{R}\)

2. The Sub-Gaussian (ψ₂) Norm

Define the ψ₂-norm by \(\|X\|_{\psi_2} := \inf\left\{ t > 0 : \mathbb{E}\left[e^{X^2/t^2}\right] \le 2 \right\}.\)

Key properties

  • The function $ t \mapsto \mathbb{E}[e^{X^2/t^2}] $ is decreasing in $ t $.
  • As $ t \to \infty $, the expectation tends to 1.
  • By monotone and dominated convergence: \(\mathbb{E}\left[e^{X^2/\|X\|_{\psi_2}^2}\right] = 2.\)

3. Example: Standard Normal

Let $ Z \sim \mathcal{N}(0,1) $.

  • Moment generating function: \(\mathbb{E}[e^{tZ}] = e^{t^2/2}\)

  • ψ₂-norm: \(\|Z\|_{\psi_2} = \sqrt{8}\)

This follows from solving \(\mathbb{E}\left[e^{Z^2/t^2}\right] = 2.\)

4. Median-of-Means Estimator (Jeremy’s Presentation)

Let $ X_1, \dots, X_N $ be i.i.d. with \(\mathbb{E}[X^2] < \infty, \quad \sigma^2 = \mathrm{Var}(X).\)

Claim

There exists an estimator $ \widehat{M} $ such that \(\mathbb{P}\left(|\widehat{M} - \mu| > t \frac{\sigma}{\sqrt{N}}\right) \le 2 e^{-c t^2}, \quad 0 \le t \le 2.\)

Construction

  • Divide data into $ B $ blocks of equal length $ L $: \(L = \left\lceil \frac{4N}{t^2} \right\rceil, \quad B = \left\lfloor \frac{N}{L} \right\rfloor.\)

  • Ignore leftover samples so that $ BL \le N $.
  • Define block means: \(\widehat{M}_b = \frac{1}{L} \sum_{i \in \text{block } b} X_i.\)
  • Final estimator: \(\widehat{M} = \mathrm{median}\{\widehat{M}_1, \dots, \widehat{M}_B\}.\)

Step 1: Control a Single Block

By Chebyshev, \(\mathbb{P}\left(|\widehat{M}_b - \mu| \ge t \frac{\sigma}{\sqrt{N}}\right) \le \frac{\sigma^2/L}{t^2\sigma^2/N} = \frac{N}{Lt^2} \le \frac{1}{4}.\)

Define event $ A_b $ as this deviation event.

Step 2: Median Argument

If at least half the block means are “bad,” the median is bad: \(\mathbb{P}(\widehat{M} \ge \mu + t\sigma/\sqrt{N}) \le \mathbb{P}\left(\sum_{b=1}^B \mathbf{1}_{A_b} \ge \frac{B}{2}\right).\)

Step 3: Generalized Hoeffding

For independent $ Y_i \in [a_i,b_i] $, \(\mathbb{P}\left(\sum (Y_i - \mathbb{E}Y_i) \ge s\right) \le \exp\left(-\frac{2s^2}{\sum (b_i - a_i)^2}\right).\)

Apply to Bernoulli indicators $ \mathbf{1}_{A_b} $: \(\mathbb{P}\left(\sum \mathbf{1}_{A_b} \ge \frac{B}{2}\right) \le e^{-B/8}.\)

Step 4: Lower Bound on Number of Blocks

Using algebra and $ t \ge 2 $, \(B \ge c t^2,\) which yields \(\mathbb{P}(|\widehat{M} - \mu| > t\sigma/\sqrt{N}) \le 2 e^{-c t^2}.\)

Instructor remark:
Despite the nice tail behavior, constants are poor and the estimator is not uniformly better than the sample mean.

5. Sum of Independent Sub-Gaussians

Theorem

Let $ X_1, \dots, X_N $ be independent, mean-zero, sub-Gaussian. Then \(\sum_{k=1}^N X_k \text{ is sub-Gaussian}, \quad \left\|\sum X_k\right\|_{\psi_2}^2 \le C \sum \|X_k\|_{\psi_2}^2.\)

Proof Sketch

Using independence: \(\mathbb{E}\left[e^{\lambda \sum X_k}\right] = \prod \mathbb{E}[e^{\lambda X_k}] \le \prod e^{C\lambda^2\|X_k\|_{\psi_2}^2} = e^{C\lambda^2\sum \|X_k\|_{\psi_2}^2}.\)

6. $ L_{\psi_2} $ Is a Normed Space

Define \(L_{\psi_2} := \{Y : \|Y\|_{\psi_2} < \infty\}.\)

Properties:

  1. Closed under finite sums
  2. Closed under scalar multiplication

Hence $ L_{\psi_2} $ is a vector space.

7. Generalized Hoeffding (Sub-Gaussian Version)

If $ X_k $ are independent, mean-zero, sub-Gaussian: $$ \mathbb{P}\left(\left|\sum X_k\right| > t\right) \le 2 \exp\left(

  • c \frac{t^2}{\sum |X_k|_{\psi_2}^2} \right). $$

Weighted version: $$ \mathbb{P}\left(\left|\sum a_k X_k\right| > t\right) \le 2 \exp\left(

  • c \frac{t^2}{\max_k |X_k|_{\psi_2}^2 |a|_2^2} \right). $$

8. Centering Lemma

\[\|X - \mathbb{E}X\|_{\psi_2} \le C \|X\|_{\psi_2}.\]

Proof uses triangle inequality and \(|\mathbb{E}X| \le C\|X\|_{\psi_2}.\)

9. Sub-Exponential Random Variables

A RV is sub-exponential if \(\mathbb{P}(|X| > t) \le 2e^{-ct}.\)

Examples:

  • $ Z^2 $ where $ Z \sim \mathcal{N}(0,1) $ (χ²)
  • Exponential, Gamma, Poisson

10. ψ₁ Norm (Sub-Exponential Norm)

\[\|X\|_{\psi_1} := \inf\left\{ t > 0 : \mathbb{E}[e^{|X|/t}] \le 2 \right\}.\]

Example: Exponential($\lambda$)

\(\mathbb{E}[e^{tX}] = \frac{\lambda}{\lambda - t}, \quad t < \lambda\)

Solving gives: \(\|X\|_{\psi_1} = \frac{2}{\lambda}, \quad \mathbb{E}X = \frac{1}{\lambda}.\)

11. Key Moral

  • Sub-Gaussian → Gaussian-type tails
  • Squaring a sub-Gaussian yields sub-exponential behavior
  • ψ-norms encode tail decay cleanly
  • One inequality unlocks many results

Next lecture: deeper study of sub-exponential variables and concentration inequalities.

Edit this page on GitHub

Comments