High Dimensional Probability — Lecture 2
January 14
Last time:
- Hoeffding inequality
- Chernoff inequality
Orlicz Spaces
Let ψ : ℝ⁺ → ℝ⁺ satisfy:
- ψ(0) = 0
- ψ increasing, ψ’ ≥ 0
- convex, ψ’’ ≥ 0
- ψ(x) → ∞ as x → ∞
Examples
-
ψ(x) = x^p, p ≥ 1
-
ψ₂(x) = e^{x²} − 1, x ≥ 0 (sub-Gaussian)
-
ψ₁(x) = e^{x} − 1, x ≥ 0 (sub-exponential)
Orlicz Norm
\[\|X\|_\psi = \inf \left\{ t > 0 : \mathbb{E}\left[ \psi\left( \frac{|X|}{t} \right) \right] \le 1 \right\}\]Define: \(L_\psi = \{ X : \|X\|_\psi < \infty \}\)
Properties of the Norm
-
Triangle inequality: \(\|X + Y\|_\psi \le \|X\|_\psi + \|Y\|_\psi\)
-
Scaling: \(\|cX\|_\psi = |c| \|X\|_\psi\)
Example 1: Lᵖ Norm
If ψ(x) = x^p, p ≥ 1:
\[\|X\|_{L^p} = \left( \mathbb{E}|X|^p \right)^{1/p}\]This recovers the usual Lᵖ norm.
Example 2: Sub-Gaussian Norm
Let ψ₂(x) = e^{x²} − 1.
\[\mathbb{E}\left[ \psi_2\left( \frac{|X|}{t} \right) \right] = \mathbb{E}\left[ e^{X^2 / t^2} − 1 \right] \le 1\]Thus: \(\mathbb{E}\left[ e^{X^2 / t^2} \right] \le 2\)
Define: \(L_{\psi_2} = \{ \text{sub-Gaussian random variables} \}\)
Every bounded random variable is sub-Gaussian.
For Z ~ N(0,1): \(\|Z\|_{\psi_2} = \sqrt{\frac{8}{3}}\)
Absolute Constants
An absolute constant is a constant that does not depend on X.
Characterizations of Sub-Gaussian Random Variables
Let X be a random variable. There exist constants k₁, k₂, k₃, k₄, k₅ > 0 such that the following are equivalent:
-
Tail bound: \(\mathbb{P}(|X| > t) \le 2 e^{-t^2 / k_1^2}, \quad t > 0\)
-
Moment growth: \(\|X\|_{L^p} \le k_2 \sqrt{p}, \quad p \ge 1\)
-
MGF of X²: \(\mathbb{E}[e^{\lambda X^2}] \le e^{k_3^2 \lambda}, \quad |\lambda| < \frac{1}{k_3}\)
-
Orlicz norm: \(\mathbb{E}\left[ e^{X^2 / k_4^2} \right] \le 2 \quad \Rightarrow \quad \|X\|_{\psi_2} \le k_4\)
-
MGF of X (mean zero): If $\mathbb{E}X = 0$, then \(\mathbb{E}[e^{\lambda X}] \le e^{k_5^2 \lambda^2}, \quad \lambda \in \mathbb{R}\)
(Most important)
Unified Form (Using ψ₂-Norm)
1. \(\mathbb{P}(|X| \ge t) \le 2 e^{-c t^2 / \|X\|_{\psi_2}^2}\)
2. \(\|X\|_{L^p} \le C \|X\|_{\psi_2} \sqrt{p}, \quad p \ge 1\)
4. \(\mathbb{E}\left[ e^{X^2 / \|X\|_{\psi_2}^2} \right] \le 2\)
5. If $\mathbb{E}X = 0$, then \(\mathbb{E}[e^{\lambda X}] \le e^{C \lambda^2 \|X\|_{\psi_2}^2}, \quad \lambda \in \mathbb{R}\)
If X is bounded
Then X is sub-Gaussian (easy to show).
Proof Sketches of Equivalences
(1) ⇒ (2)
\[\mathbb{E}|X|^p = \int_0^\infty p t^{p-1} \mathbb{P}(|X| > t)\, dt\]Assume k₁ = 1.
\[\le \int_0^\infty p t^{p-1} e^{-t^2} dt\]Use Gamma function.
Gamma Function
\[\Gamma(\alpha) = \int_0^\infty t^{\alpha - 1} e^{-t} dt\] \[\Gamma(n) = (n-1)! \quad \text{for } n \in \mathbb{N}\]Change of variables: s = t²
\[= p \int_0^\infty s^{p/2 - 1} e^{-s} ds = p \Gamma(p/2) \le 3 p^{p/2}\]Thus: \(\|X\|_{L^p} \le C \sqrt{p}\)
(2) ⇒ (3)
WLOG let k₂ = 1.
Taylor series: \(\mathbb{E}[e^{\lambda X^2}] = \mathbb{E}\left[ 1 + \sum_{p=1}^\infty \frac{\lambda^p X^{2p}}{p!} \right]\)
\[\le 1 + \sum_{p=1}^\infty \frac{\lambda^p \mathbb{E}[X^{2p}]}{p!}\]Use: \(\mathbb{E}[X^{2p}] \le (2p)^p\)
Stirling formula: \(p! \ge (p/e)^p\)
\[\le 1 + \sum_{p=1}^\infty (2e\lambda)^p\]Geometric series converges if $ \lambda < \frac{1}{2e} $.
(3) ⇒ (4)
Trivial: \(\mathbb{E}[e^{X^2 / k_3^2}] \le e^{k_3^2} \Rightarrow k_4^2 = k_3^2 / \log 2\)
(4) ⇒ (1)
WLOG k₄ = 1.
\[\mathbb{P}(|X| > t) = \mathbb{P}(e^{X^2} > e^{t^2}) \le e^{-t^2} \mathbb{E}[e^{X^2}] \le 2 e^{-t^2}\](Markov)
(5) ⇒ (1)
Assume k₅ = 1, λ > 0.
\[\mathbb{P}(X > t) = \mathbb{P}(e^{\lambda X} > e^{\lambda t}) \le e^{-\lambda t} \mathbb{E}[e^{\lambda X}] \le e^{-\lambda t + \lambda^2}\]Let λ = t/2: \(\le e^{-t^2/4} \Rightarrow k_1 = 2\)
(3) ⇒ (5)
Assume k₃ = 1.
Claim: \(e^{\lambda X} \le X + e^{\lambda^2 X^2}\) (Taylor series argument)
Since $ \mathbb{E}X = 0 $:
\[\mathbb{E}[e^{\lambda X}] \le \mathbb{E}[e^{\lambda^2 X^2}] \le e^{\lambda^2}\]| Restriction: | \lambda | ≤ 1. |
If |\lambda| > 1, use: \(\lambda X \le \frac{\lambda^2}{2} + \frac{X^2}{2}\)
Then: \(\mathbb{E}[e^{\lambda X}] \le e^{\lambda^2/2} \mathbb{E}[e^{X^2/2}] \le e^{\lambda^2}\)
Which recovers (5).
Comments