Lecture 5: Geometric Discrepancy and Orlicz Norms
A single norm for every tail scale
Lecture 4 fixed one tail scale — the Gaussian, quadratic one — and built a calculus around it. Many random variables genuinely live on a different scale: a squared Gaussian, for instance, has an exponential rather than a Gaussian tail. Orlicz norms package every scale into a single family of norms, so that sub-Gaussian behavior becomes one member (\(\psi_2\)) of a larger, algebraically well-behaved family. We end with a genuine two-dimensional application: bounding how unevenly \(n\) random points can be spread across the unit square.
1 Orlicz norms
Definition 1 (The \(\psi_\alpha\) norm) For \(0<\alpha<\infty\) and a random variable \(X\), \[ \|X\|_{\psi_\alpha}:=\inf\left\{t>0:\mathbb E\left(e^{|X|^\alpha/t^\alpha}-1\right)\leq1\right\}. \]
Show that \(\|\cdot\|_{\psi_\alpha}\) is a genuine norm for \(\alpha\in[1,\infty)\) (only a quasi-norm, satisfying the triangle inequality up to a constant, for \(\alpha<1\)).
The case \(\alpha=2\) is the sub-Gaussian norm, already used informally in Lecture 4; general \(\alpha\) interpolates between it and heavier-tailed scales — \(\alpha=1\) is the sub-exponential norm.
2 Sub-Gaussian variables and the \(\psi_2\) norm
Lemma 1 (Sub-Gaussian variables and the \(\psi_2\) norm) If \(X\) is mean-zero and \(V\)-subgaussian, then \(\|X\|_{\psi_2}\leq2\sqrt V\). Conversely, for any \(X\), \[ |\mathbb EX|\leq\sqrt{\mathbb EX^2}\leq\|X\|_{\psi_2}, \] and a mean-zero \(X\) with \(\|X\|_{\psi_2}<\infty\) is sub-Gaussian with variance proxy \(C\|X\|_{\psi_2}^2\) for an absolute constant \(C\).
Forward direction. Let \(Z\sim N(0,1)\) be independent of \(X\) and fix \(\alpha^2=1/(2V)\). Using \(\mathbb E_Ze^{\alpha ZX}=e^{\alpha^2X^2/2}\) (the Gaussian moment generating function evaluated at \(\alpha X\)) and Fubini, \[ \mathbb Ee^{\alpha^2X^2/2} =\mathbb E_X\,\mathbb E_Ze^{\alpha ZX} =\mathbb E_Z\,\mathbb E_Xe^{\alpha ZX} \leq\mathbb E_Ze^{\alpha^2Z^2V/2} =\frac1{\sqrt{1-\alpha^2V}}=\sqrt2, \] using that \(X\) is \(V\)-subgaussian with \(\lambda=\alpha Z\), and the Gaussian identity \(\mathbb Ee^{\theta Z^2/2}=(1-\theta)^{-1/2}\) for \(\theta<1\). Since \(\alpha^2/2=1/(4V)\), this says \(\mathbb E\exp(X^2/(4V))\leq\sqrt2\leq2\), so \(t=2\sqrt V\) satisfies the defining property, giving \(\|X\|_{\psi_2}\leq2\sqrt V\).
Converse, first claim. Write \(t=\|X\|_{\psi_2}\). The elementary inequality \(s\leq e^s-1\) for \(s\geq0\), applied to \(s=X^2/t^2\), gives \(X^2\leq t^2(e^{X^2/t^2}-1)\) pointwise. Taking expectations, \(\mathbb EX^2\leq t^2\cdot\mathbb E(e^{X^2/t^2}-1)\leq t^2\), and \(|\mathbb EX|\leq\sqrt{\mathbb EX^2}\leq t\).
Converse, second claim. With \(t=\|X\|_{\psi_2}\), \(\mathbb Ee^{X^2/t^2}\leq2\). For any \(\lambda\), Young’s inequality \(\lambda x\leq x^2/2t^2+\lambda^2t^2/2\) gives \(e^{\lambda X}\leq e^{X^2/2t^2}e^{\lambda^2t^2/2}\), and Cauchy–Schwarz gives \(\mathbb Ee^{X^2/2t^2}\leq\sqrt{\mathbb Ee^{X^2/t^2}}\leq\sqrt2\). So \(\mathbb Ee^{\lambda X}\leq\sqrt2\,e^{\lambda^2t^2/2}\) for every \(\lambda\); a standard absorption of the constant prefactor (increasing the exponent by a fixed multiplicative factor) turns this into a genuine sub-Gaussian bound \(\mathbb Ee^{\lambda X}\leq e^{\lambda^2Ct^2/2}\) for an absolute constant \(C\).
Generalize the forward direction: if \(\mathbb P\{|X|\geq t\}\leq Ae^{-t/\sigma^\alpha}\) for every \(t\geq0\), show \(\|X\|_{\psi_\alpha}\leq C_\alpha(A)\sigma\) for a constant depending only on \(\alpha\) and \(A\).
3 Equivalent ways to measure a tail scale
For a random variable \(X\) and \(\alpha\in(0,\infty)\), define the moment norm \[ \|X\|_{\text{sub-}\alpha}:=\sup_{p\in\mathbb N}\left[(\mathbb E|X|^{2p})^{1/2p}\,p^{-1/\alpha}\right]. \] This is trivially a (quasi-)norm for every \(\alpha\).
Theorem 1 (Three ways to measure a tail scale) Fix \(\alpha\in(0,\infty)\) and \(A>2\). For a random variable \(X\), the following are equivalent up to changes in constants depending only on \(\alpha\) (and, for the first, on \(A\)):
- \(\displaystyle\inf\Big\{\sigma>0:\sup_{t>0}\mathbb P\{|X|\geq t\}\,e^{t^\alpha/\sigma^\alpha}\leq A\Big\}<\infty\);
- \(\|X\|_{\text{sub-}\alpha}<\infty\);
- \(\|X\|_{\psi_\alpha}<\infty\).
We prove \((1)\Rightarrow(3)\Rightarrow(1)\) and \((1)\Rightarrow(2)\Rightarrow(1)\); together these give all three pairwise equivalences. Fix \(\sigma\) so that \(\mathbb P\{|X|\geq t\}\leq Ae^{-t^\alpha/\sigma^\alpha}\) for every \(t\geq0\) (the content of (1)).
\((1)\Rightarrow(3)\). Let \(t=(A+1)^{1/\alpha}\sigma\) and \(Y=|X|^\alpha/t^\alpha\geq0\). For any nonnegative random variable \(Y\), \[ e^Y-1=\int_0^Ye^y\,dy=\int_0^\infty e^y\mathbb 1\{y<Y\}\,dy, \] so taking expectations and applying Tonelli’s theorem to the nonnegative integrand, \[ \mathbb E(e^Y-1)=\int_0^\infty e^y\,\mathbb P\{Y>y\}\,dy. \] Since \(\mathbb P\{Y>y\}=\mathbb P\{|X|>ty^{1/\alpha}\}\leq Ae^{-t^\alpha y/\sigma^\alpha}=Ae^{-(A+1)y}\), \[ \mathbb E(e^Y-1)\leq A\int_0^\infty e^{y-(A+1)y}\,dy=A\int_0^\infty e^{-Ay}\,dy=1. \] So \(t\) satisfies the defining property of \(\|X\|_{\psi_\alpha}\), giving \(\|X\|_{\psi_\alpha}\leq t=(A+1)^{1/\alpha}\sigma\).
\((3)\Rightarrow(1)\). Let \(t=\|X\|_{\psi_\alpha}\), so \(\mathbb Ee^{|X|^\alpha/t^\alpha}\leq2\). Markov’s inequality applied to the nonnegative variable \(e^{|X|^\alpha/t^\alpha}\) gives, for every \(s\geq0\), \[ \mathbb P\{|X|\geq s\}=\mathbb P\!\left\{e^{|X|^\alpha/t^\alpha}\geq e^{s^\alpha/t^\alpha}\right\} \leq e^{-s^\alpha/t^\alpha}\,\mathbb Ee^{|X|^\alpha/t^\alpha}\leq2e^{-s^\alpha/t^\alpha}. \] This is exactly (1), with \(\sigma=t\) and prefactor \(2\); since (1) holds for any fixed target \(A>2\) once it holds with prefactor \(2\leq A\), this proves \((3)\Rightarrow(1)\).
\((1)\Rightarrow(2)\). For any real \(r>0\), write \(\mathbb E|X|^r\) as a tail integral and substitute \(u=t^\alpha/\sigma^\alpha\) (so \(t=\sigma u^{1/\alpha}\), \(dt=\frac\sigma\alpha u^{1/\alpha-1}du\)): \[ \mathbb E|X|^r=r\int_0^\infty t^{r-1}\mathbb P\{|X|\geq t\}\,dt \leq rA\int_0^\infty t^{r-1}e^{-t^\alpha/\sigma^\alpha}\,dt =\frac{rA\sigma^r}\alpha\int_0^\infty u^{r/\alpha-1}e^{-u}\,du =A\sigma^r\,\Gamma\!\left(\frac r\alpha+1\right), \] using the identity \(\frac r\alpha\Gamma(r/\alpha)=\Gamma(r/\alpha+1)\). Taking \(r=2p\) for an integer \(p\geq1\), \[ (\mathbb E|X|^{2p})^{1/2p}\leq A^{1/2p}\sigma\,\Gamma\!\left(\frac{2p}\alpha+1\right)^{1/2p}. \] It remains to bound \(\Gamma(x+1)^{1/x}\) for \(x=2p/\alpha\). It can be shown, by comparing \(\ln\Gamma(x+1)\) to the integral of \(\ln\) (as in the usual elementary proof of Stirling’s approximation), that \[ \Gamma(x+1)^{1/x}\leq9(x+1)\qquad\text{for every }x\geq0. \] With \(x=2p/\alpha\), this gives \(\Gamma(2p/\alpha+1)^{1/2p}=\big[\Gamma(x+1)^{1/x}\big]^{1/\alpha}\leq\big[9(2p/\alpha+1)\big]^{1/\alpha}\leq C_\alpha\,p^{1/\alpha}\) for a constant \(C_\alpha\) depending only on \(\alpha\) (using \(p\geq1\) to absorb the \(+1\)). Combining with the displayed moment bound and \(A^{1/2p}\leq\max(A,1)^{1/2}\) for \(p\geq1\) gives \(\|X\|_{\text{sub-}\alpha}\leq C_\alpha\sqrt{\max(A,1)}\,\sigma\).
\((2)\Rightarrow(1)\). Let \(M=\|X\|_{\text{sub-}\alpha}\), fix \(s>0\), and for each integer \(p\geq1\) apply Markov’s inequality to \(|X|^{2p}\): \[ \mathbb P\{|X|\geq s\}\leq\frac{\mathbb E|X|^{2p}}{s^{2p}}\leq\left(\frac{Mp^{1/\alpha}}s\right)^{2p}. \] Treating \(p\) as a continuous variable, minimize \(\varphi(p)=2p\ln(Mp^{1/\alpha}/s)\): differentiating, \(\varphi'(p)=2\ln(Mp^{1/\alpha}/s)+\frac2\alpha=0\) at \(p^*=e^{-1}(s/M)^\alpha\), where \(Mp^{*1/\alpha}/s=e^{-1/\alpha}\) and the bound evaluates to \(\exp(-2p^*/\alpha)\).
Since \(p\) must be a positive integer, take \(p=\lceil p^*\rceil\) instead of \(p^*\) itself once \(p^*\geq1\) (i.e. once \(s\geq e^{1/\alpha}M\)); rounding up at most doubles \(p\), and plugging \(p\leq2p^*\) back into the bound above changes the resulting rate only by a constant factor depending on \(\alpha\), giving \[ \mathbb P\{|X|\geq s\}\leq\exp\!\left(-c_\alpha\left(\frac sM\right)^\alpha\right) \] for an explicit constant \(c_\alpha>0\). For \(0\leq s<e^{1/\alpha}M\), the trivial bound \(\mathbb P\{|X|\geq s\}\leq1\) is within a fixed constant of the same exponential expression, since then \((s/M)^\alpha<e\). Combining both ranges gives a tail bound of the form (1), with \(\sigma\) and the prefactor explicit functions of \(\alpha\) alone; rescaling \(\sigma\) by a further constant factor brings the prefactor down to any target \(A>2\).
4 Products of Orlicz norms
Lemma 2 (An Orlicz–Hölder inequality) If \(\frac1\beta+\frac1\gamma=\frac1\alpha\), then for any random variables \(X,Y\), \[ \|XY\|_{\psi_\alpha}\leq\|X\|_{\psi_\beta}\|Y\|_{\psi_\gamma}. \]
By homogeneity it suffices to treat \(\|X\|_{\psi_\beta}\leq1\), \(\|Y\|_{\psi_\gamma}\leq1\), and show \(\|XY\|_{\psi_\alpha}\leq1\). Young’s inequality with conjugate exponents \(\beta/\alpha,\gamma/\alpha\) gives \[ |XY|^\alpha\leq\frac\alpha\beta|X|^\beta+\frac\alpha\gamma|Y|^\gamma, \] hence \(e^{|XY|^\alpha}\leq e^{\frac\alpha\beta|X|^\beta}e^{\frac\alpha\gamma|Y|^\gamma}\). Hölder’s inequality (with the same conjugate exponents) gives \[ \mathbb Ee^{|XY|^\alpha} \leq\big(\mathbb Ee^{|X|^\beta}\big)^{\alpha/\beta}\big(\mathbb Ee^{|Y|^\gamma}\big)^{\alpha/\gamma} \leq2^{\alpha/\beta}\cdot2^{\alpha/\gamma}=2, \] using \(\|X\|_{\psi_\beta},\|Y\|_{\psi_\gamma}\leq1\) and \(\alpha/\beta+\alpha/\gamma=1\).
Taking \(Y=X\) and \(\beta=\alpha\), \(\gamma=1\) in the identity underlying the lemma gives \(\||X|^\alpha\|_{\psi_1}=\|X\|_{\psi_\alpha}^\alpha\): for a standard Gaussian \(X\), \(\|X\|_{\psi_2}<\infty\), so \(X^2\) is sub-exponential (\(\|X^2\|_{\psi_1}=\|X\|_{\psi_2}^2<\infty\)) but not sub-Gaussian (\(\|X^2\|_{\psi_2}=\infty\)). Squares of Gaussians are the model example for the heavier, \(\psi_1\) tail that Bernstein’s inequality will handle.
5 Sums of independent sub-Gaussians
Theorem 2 (Sums of independent sub-Gaussians (a Pythagorean theorem)) Let \(X_1,\ldots,X_n\) be independent, mean-zero, and sub-Gaussian with variance proxies \(\sigma_1^2,\ldots,\sigma_n^2\). Then \[ S_n=\sum_{i=1}^nX_i \] is sub-Gaussian with variance proxy \(\sum_i\sigma_i^2\). In particular, \[ \mathbb P\{|S_n|\geq t\} \leq2\exp\left(-\frac{t^2}{2\sum_i\sigma_i^2}\right). \]
Independence factors the exponential moment: \[ \mathbb Ee^{\lambda S_n} =\prod_{i=1}^n\mathbb Ee^{\lambda X_i} \leq\prod_{i=1}^n e^{\lambda^2\sigma_i^2/2} =\exp\left(\frac{\lambda^2}{2}\sum_i\sigma_i^2\right). \] Apply the sub-Gaussian tail bound from Lecture 4.
Combining this with Hoeffding’s lemma from Lecture 4 produces Hoeffding’s inequality for sums of independent bounded variables. It is worth checking this scale directly on a Bernoulli variable.
Corollary 1 (Every Bernoulli is \(1\)-subgaussian) For every \(p\in[0,1]\), \(X\sim\operatorname{Ber}(p)\) is \(1\)-subgaussian. Consequently \(\operatorname{Binomial}(n,p)\) is \(n\)-subgaussian for every \(p\).
Let \(\widetilde X\) be an independent copy of \(X\). Convexity of \(\lambda\mapsto e^{\lambda x}\) and Jensen’s inequality give the standard symmetrization bound \[ \mathbb Ee^{\lambda(X-\mathbb EX)}\leq\mathbb Ee^{\lambda(X-\widetilde X)}. \] Here \(X-\widetilde X\) equals \(\pm1\) each with probability \(p(1-p)\), and \(0\) otherwise, so \[ \mathbb Ee^{\lambda(X-\widetilde X)} =1+2p(1-p)(\cosh\lambda-1) \leq\frac12+\frac12\cosh\lambda, \] using \(p(1-p)\leq1/4\). Since \(\cosh\lambda\leq e^{\lambda^2/2}\) and \(e^{\lambda^2/2}\geq1\), the right side is at most \(e^{\lambda^2/2}\).
This is weaker than the constant \(1/4\) that Hoeffding’s lemma gives (which uses boundedness directly), but the symmetrization technique behind it generalizes far beyond bounded variables. It is worth comparing this generic proxy to the true variance: applying Theorem 2 to \(n\) i.i.d. \(\operatorname{Ber}(p)\) variables gives \(\mathbb P\{|S_n-np|\geq t\}\leq2\exp(-t^2/2n)\) (or \(\leq2\exp(-2t^2/n)\) using Hoeffding’s tighter \(1/4\)). The true variance is \(np(1-p)\). When \(p\) is well separated from \(\{0,1\}\), this is within a constant factor of \(n\), so the bound is essentially accurate; but as \(p\to0\), the true variance \(np(1-p)\approx np\) is far smaller than the generic proxy, and the bound is off by a factor of order \(1/p\) in the exponent — exactly the regime where Lecture 4’s Poisson-specific moderate-deviations bound is the right tool instead.
6 Geometric discrepancy
Throw \(n\) i.i.d. points \(X_1,\ldots,X_n\) uniformly in \([0,1]^2\). For an axis-aligned rectangle \(I\subseteq[0,1]^2\), let \(N(I)=\#\{i:X_i\in I\}\), so \(N(I)\sim\operatorname{Binomial}(n,|I|)\) where \(|I|\) is the area of \(I\). By Corollary 1 and Theorem 2, \(N(I)\) is \(n\)-subgaussian for every fixed rectangle \(I\): \[ \mathbb P\{|N(I)-n|I||\geq t\}\leq2\exp\left(-\frac{t^2}{2n}\right). \] This controls one rectangle at a time. How badly can the counts be off simultaneously, over every rectangle at once?
Theorem 3 (Discrepancy of a random point set) There is an absolute constant \(C\) such that, with probability tending to \(1\) as \(n\to\infty\), \[ \sup_{I\subseteq[0,1]^2\text{ rectangle}}|N(I)-n|I||\leq C\sqrt{n\log n}. \]
Step 1: a fine net. Let \(\mathcal S\) be the set of rectangles whose corners lie on the grid \((n^{-100}\mathbb Z)\cap[0,1]\); there are at most \(n^{400}\) of them. A union bound over \(\mathcal S\) gives \[ \mathbb P\Big\{\sup_{I\in\mathcal S}|N(I)-n|I||\geq C\sqrt{n\log n}\Big\} \leq n^{400}\cdot2\exp\left(-\frac{C^2\log n}2\right) =2n^{400-C^2/2}\longrightarrow0 \] once \(C\) is large enough that \(C^2/2>400\).
Step 2: approximating an arbitrary rectangle. For a general rectangle \(I\), round each of its four coordinates to the nearest grid point to get \(\widehat I\in\mathcal S\). The symmetric difference \(I\,\triangle\,\widehat I\) is contained in a union of thin boundary strips of width at most \(n^{-100}\). Each such strip \(J\) has area \(O(n^{-100})\), so \(N(J)\) is a Poisson-Binomial-type count with mean \(\mu=n|J|=O(n^{-99})\); the Poisson tail bound from Lecture 4 gives \(\mathbb P\{N(J)\geq1\}\leq e\mu=O(n^{-99})\), and a union bound over the \(O(n^{100})\) relevant grid strips still tends to \(0\). So with high probability every such strip is empty, and \[ |N(I)-n|I|| \leq|N(I)-N(\widehat I)|+|N(\widehat I)-n|\widehat I||+n\big||\widehat I|-|I|\big| \leq0+C\sqrt{n\log n}+O(n^{-99}), \] using Step 1 for the middle term. Taking the supremum over \(I\) (which forces \(\widehat I\) to range only over the finite net \(\mathcal S\)) proves the claim.
This two-step strategy — control a fine net by a union bound, then bound the error of approximating an arbitrary point by a net point — is the first appearance in this course of the chaining idea that will be developed in full generality later on.
7 Where we go next
We now have a genuine algebra of tail scales: \(\psi_2\) for Gaussian-type tails, \(\psi_1\) for the heavier tails that arise from products and squares, and a Hölder inequality relating them. Bernstein’s inequality, next, is the tool built for exactly the \(\psi_1\) scale, and dimension reduction gives our first serious application of the whole toolkit.