许多随机变量都会围绕均值集中；特别地，超过均值的概率通常是常数量级。下面给出一个集中性很差的例子，其中这个概率是指数小的。

设 $X_1,\ldots,X_n$ 是独立随机变量，且都服从 $[0,1]$ 上的均匀分布。证明它们的乘积

满足

Proposition 2.1.2 中的下界留作了未证结论；现在来证明它。设 $g\sim N(0,1)$。证明：对所有 $t>0$，都有

为此，把左右两边的差看作 $t$ 的函数。检查这个函数会随着 $t$ 增大而递减到 $0$。

虽然对 $g\sim N(0,1)$，Gaussian tail $\mathbb{P}\{g>t\}$ 不能对所有 $t$ 都解析地计算出来，但它可以展开成下面的级数：

其中

是 $g$ 的密度。而且，这个比值夹在该级数任意一对相邻部分和之间。例如，

按以下步骤证明 (2.30)：

(a) 检查对所有 $x$ 都有

(b) 使用 (a) 中的等式，对

分部积分。重复这个过程。

证明 $g\sim N(0,1)$ 满足：

(a) 对所有 $t>0$，

(b) 对所有 $t>0$，

证明数值界 (2.7)：

使用指数矩方法证明：若 $g\sim N(0,1)$，则

虽然这个界比 (2.3) 的常数因子更大，但在很多场景中仍然足够使用。

设 $X_1,\ldots,X_N$ 是非负、独立、具有连续分布的随机变量。假设所有 $X_i$ 的概率密度函数都被同一个常数 $K$ 一致控制。证明：对任意 $\varepsilon>0$，都有

设 $X$ 和 $Y$ 是均值相同的随机变量。假设 $X$ 取值于区间 $[a,b]$，而 $Y$ 取值于两点集 $\{a,b\}$。证明：

证明：任意取值于区间 $[a,b]$ 的随机变量 $X$ 都满足

按以下步骤证明：

(a) 说明不失一般性，可以假设 $X$ 的均值为零，$b-a=1$，并且 $X$ 只取两点集 $\{a,b\}$ 中的值。

(b) 计算累积母函数

并检查 $K(0)=K'(0)=0$ 且 $K''(\lambda)\le 1/4$。推出对所有 $\lambda\in\mathbb{R}$，都有 $K(\lambda)\le \lambda^2/8$。

从 Hoeffding lemma（Exercise 2.9）推出 Theorem 2.2.6。

证明 Remark 2.3.2 中提到的结论：在 Theorem 2.3.1 的假设下，

证明：若二项随机变量 $S_N\sim\operatorname{Binom}(N,\mu/N)$，则它满足下面的 “reverse Chernoff” 不等式：

由于 Poisson 极限定理（Theorem 1.7.6），我们有理由期待 Chernoff 不等式也适用于 Poisson 变量。确实如此。使用指数矩方法，证明对 $X\sim\operatorname{Pois}(\mu)$ 有以下尾界：

(a) Theorem 2.3.1 的版本：对每个 $t\ge\mu$，

(b) Remark 2.3.2 的版本：对每个 $0<t\le\mu$，

(c) Corollary 2.3.4 的版本：对每个 $0\le\delta\le1$，

(d) Exercise 2.12 的版本：对每个整数 $t>0$，

我们来扩展 Corollary 2.3.4。设 $X_i$ 是参数为 $p_i$ 的独立 Bernoulli 随机变量。考虑它们的和

并记其均值为 $\mu=\mathbb{E}S_N$。证明：

说明 Chernoff 不等式的所有版本（Theorem 2.3.1、Remark 2.3.2 和 Corollary 2.3.4）都适用于任意独立随机变量 $X_i$，只要它们取值于区间 $[0,1]$，且均值为 $p_i$。

Theorem 2.4.1 的证明有一个小瑕疵：$B=t^2/4$ 未必是一个能整除 $N$ 的整数。修正这个问题。

你可能会问 Theorem 2.4.1 是否对所有 $t>0$ 都成立。答案是否定的。事实上，没有任何均值估计量能对所有分位点都给出次高斯置信界。反驳下面的断言：

存在绝对常数 $c>0$，使得下述结论成立。对任意整数 $N>0$ 和每个 $t\ge0$，都可以找到一个函数 $\widehat{\mu}:\mathbb{R}^N\to\mathbb{R}$，使得对所有均值为 $\mu$、方差为 $\sigma^2$ 的 i.i.d. 随机变量 $X_1,\ldots,X_N$，都有

通过展开 Le Cam two-point method 的一个版本来完成：

(a) 考虑两个随机向量 $\mathbf{X}=(X_1,\ldots,X_N)$ 和 $\mathbf{Y}=(Y_1,\ldots,Y_N)$，它们的坐标独立，且 $X_i\sim\operatorname{Lap}(0,1)$、$Y_i\sim\operatorname{Lap}(\mu,1)$，其中 $\mu>0$。检查：对任意可测集合 $B\subset\mathbb{R}^N$，都有

(b) 反设上述断言成立。将其用于控制事件 $|\widehat{\mu}(\mathbf{X})|\ge\mu/2$ 和 $|\widehat{\mu}(\mathbf{Y})-\mu|\ge\mu/2$ 的概率。

(c) 选取足够大的 $\mu$，并使用 (a) 把 $\mathbf{Y}$ 替换为 $\mathbf{X}$，使两个事件 $|\widehat{\mu}(\mathbf{X})|\lt\mu/2$ 与 $|\widehat{\mu}(\mathbf{X})-\mu|\lt\mu/2$ 都以较大概率发生。用三角不等式推出矛盾。

在 Exercise 1.10 中，我们看到典型的稀疏随机图 $G\sim G(n,p)$ 会有孤立顶点，因此最小度为零。不过，大多数顶点度仍然接近期望度 $d=(n-1)p$。证明：存在绝对常数 $C>0$，使得若 $d\ge C$，则至少以 $0.99$ 的概率发生下述事件：至少 $99\%$ 的顶点，其度数都位于 $0.9d$ 和 $1.1d$ 之间。

在 Exercise 1.10 中，我们观察到典型的稀疏随机图 $G\sim G(n,p)$ 的最小度为零。那么最大度 $\Delta(G)$ 又如何？证明：存在绝对常数 $c,c_1,c_2>0$，使得下述结论成立：若 $n\ge3$，且期望度 $d=(n-1)p$ 满足

则至少以 $0.99$ 的概率有

随机图 $G(n,p)$ 展现出一个显著性质：只要两个顶点子集 $S$ 和 $T$ 不是太小，连接它们的边数 $e(S,T)$ 就与这两个集合的大小成正比。这里 $e(S,T)$ 表示端点分别落在 $S$ 和 $T$ 中的边数。证明：存在绝对常数 $C>0$，使得至少以 $1-2^{-n}$ 的概率发生下述事件：

对所有互不相交的顶点子集 $S,T$ 都成立，只要

设想我们有一个用于解决某个判定问题的算法，例如判断 $p$ 是否为素数。假设该算法会随机作出决定，并且给出正确结果的概率为 $\frac12+\varepsilon$，其中 $\varepsilon>0$；也就是说，它只比纯猜测稍好一点。为了提高性能，运行该算法 $N$ 次并取多数投票。证明：对任意 $\delta\in(0,1)$，只要

多数投票的答案至少以 $1-\delta$ 的概率正确。

设 $g\sim N(0,1)$。

(a) 用 Gamma 函数表示 $g$ 的绝对矩：

(b) 推出 $g$ 的 $L^p$ 范数满足

你可能会问，为什么 Proposition 2.6.1 的性质 (iv) 中要假设 $\mathbb{E}X=0$。证明：任何满足该性质的随机变量 $X$ 都必须有零均值。

检查以下结论。

(a) Constant：若 $X=c$ a.s.，其中 $c$ 是常数，则

(b) Bounded：若 $X$ a.s. 有界，则

(c) Rademacher：Rademacher 随机变量 $X$ 满足

(d) Normal：若 $X\sim N(0,\sigma^2)$，则

(e) Bernoulli：若 $X\sim\operatorname{Ber}(p)$，则

解释为什么 exponential、Poisson、geometric、chi-squared、Gamma、Cauchy 和 Pareto 分布都不是次高斯分布。

在 Proposition 2.6.1 中，我们已经见过几种等价描述次高斯分布的方法。这里还有一种。证明：随机变量 $X$ 是次高斯的，当且仅当存在 $K>0$，使得

更精确地，证明：若 $X$ 是次高斯，则 (2.31) 对 $K=\|X\|_{\psi_2}$ 成立。反过来，若 (2.31) 成立，则 $X$ 是次高斯，并且

对两个随机变量 $X$ 和 $Y$，若

则记 $X\preceq Y$。

(a) 证明：$X$ 是次高斯的，当且仅当存在 $K>0$，使得

更精确地，证明：若 $X$ 是次高斯，则 (2.33) 对某个 $K\le C\|X\|_{\psi_2}$ 成立。反过来，若 (2.33) 成立，则 $X$ 是次高斯，并且 $\|X\|_{\psi_2}\le CK$。照例，$C$ 表示你选择的某个绝对常数。

(b) 举例说明：如果把 (2.32) 中的因子 $2$ 换成 $1$，则 (a) 可能失败。

对两个随机变量 $X$ 和 $Y$，若对任意凸且递增的函数 $\Phi:\mathbb{R}\to\mathbb{R}$ 都有

则记 $X\precsim Y$。证明：$X$ 是次高斯的，当且仅当存在 $K>0$，使得

更精确地，证明：若 $X$ 是次高斯，则 (2.34) 对某个 $K\le C\|X\|_{\psi_2}$ 成立。反过来，若 (2.34) 成立，则 $X$ 是次高斯，并且 $\|X\|_{\psi_2}\le CK$。

从次高斯 Hoeffding 不等式（Theorem 2.7.3）推出有界随机变量的 Hoeffding 不等式（Theorem 2.2.6），指数中的常数可以不是 $2$，只需是另一个绝对常数。

设 $X_1,\ldots,X_N$ 是独立次高斯随机变量，均值为零、方差为一，并设 $a_1,\ldots,a_N\in\mathbb{R}$。证明：

其中

且 $c>0$ 是一个绝对常数。这个结果是 Example 1.5.1 的一个一般定量版本，不过它没有达到精确概率 $1/2$。

设 $X_1,X_2,\ldots$ 是 i.i.d. 随机变量，并且对任意 $N$、任意系数向量 $\mathbf{a}\in\mathbb{R}^N$，它们都满足类似 Hoeffding 的不等式 (2.14)，其中常数 $c>0$ 与 $N$ 和 $\mathbf{a}$ 无关。证明：

证明：任意两个独立、均值为零的次高斯随机变量 $X$ 和 $Y$ 都满足

其中 $\asymp$ 表示相差绝对常数因子。

鉴于 Pythagorean identity (2.19)，一个自然问题是 Proposition 2.7.1 中的不等式能否反过来。在本题和下一题中，你将说明：若 $X_i$ 同分布，答案是“可以”；但一般情形下答案是“不可以”。

(a) 设 $X,X_1,X_2,\ldots,X_N$ 是 i.i.d.、均值为零的次高斯随机变量。证明：

其中 $\asymp$ 表示相差绝对常数因子。

(b) 推出：若 $S_N\sim\operatorname{Binom}(N,p)$，则

(a) 找到独立、均值为零的次高斯随机变量 $X_1,X_2,\ldots$，使得对任意 $N$ 和任意系数向量 $a=(a_1,\ldots,a_N)\in\mathbb{R}^N$，都有

其中 $\asymp$ 表示相差绝对常数因子。

(b) 推出：Proposition 2.7.1 中的不等式一般不能反向成立。

在 Exercise 1.12 中，我们展示了如何用随机变量 $X$ 的 $L^1$ 和 $L^\infty$ 范数来控制它的 $L^p$ 范数。现在证明一个针对次高斯范数的类似结果。

(a) 证明：若 $\|X\|_{L^1}=a$ 且 $\|X\|_{L^\infty}=b$，则

其中 $C$ 是绝对常数。

(b) 给出一个例子说明：对任意 $a$ 和 $b$，(a) 中的界在绝对常数因子意义下都是紧的。

在 Theorem 2.7.5 中，我们证明了 $p\in[2,\infty)$ 的 Khintchine 不等式。现在把它扩展到 $p\in[1,2]$。

(a) Extrapolation：证明任意具有有限 $L^3$ 范数的随机变量 $Z$ 都满足

(b) 设 $X_1,\ldots,X_N$ 是独立次高斯随机变量，均值为零、方差为一，并设 $a_1,\ldots,a_N\in\mathbb{R}$。证明：

其中 $K=\max_i\|X_i\|_{\psi_2}$，且 $c>0$ 是绝对常数。

(c) 推出：对任意 $p\in[1,2]$，同样的不等式对这个和的 $L^p$ 范数也成立。

证明 Proposition 2.7.6 的下面这个强化版本。设 $X_1,X_2,\ldots$ 是一列次高斯随机变量，不要求独立。那么

其中 $C$ 是绝对常数。

我们来证明标准正态随机变量的 maximal inequality (2.22) 的一个渐近 sharp 版本。

(a) 设 $g_1,\ldots,g_N$ 是 $N(0,1)$ 随机变量，其中 $N\ge2$，不要求它们独立。证明：

(b) 证明：若 $g_1,g_2,\ldots$ 是独立的 $N(0,1)$ 随机变量，则当 $N\to\infty$ 时，

证明：随机变量 $X$ 是次高斯的，当且仅当存在 $K>0$，使得

其中 $X_i$ 是 $X$ 的独立副本。我们已经证明了这个命题的一半：Proposition 2.7.6 表明，如果 $X$ 是次高斯的，则 (2.35) 对 $K\le C\|X\|_{\psi_2}$ 成立。现在证明反方向：若 (2.35) 成立，则 $X$ 是次高斯的，并且 $\|X\|_{\psi_2}\le CK$。

你可能已经注意到，涉及次高斯范数的大多数结果只是在绝对常数因子意义下成立，而不是精确成立。为了细化这些结果，我们可以使用 Proposition 2.6.1 中的等价性质 (iv) 重新定义次高斯范数。作为动机，回忆若 $X\sim N(\mu,\sigma^2)$，则对所有 $\lambda\in\mathbb{R}$，都有

受此启发，定义随机变量 $X$ 的 subgaussian variance 为

回忆 $X$ 的 $L^2$ 范数可以写成

受此启发，通过下面的恒等式定义随机变量 $X$ 的 exact subgaussian norm：

证明以下结论。

(a) exact subgaussian norm 确实在次高斯随机变量空间上定义了一个范数。

(b) exact subgaussian norm 与标准次高斯范数在绝对常数因子意义下等价：

(c) 有

并且当 $X$ 是正态分布时，上述不等式取等号。

(d) 若 $X_1,\ldots,X_N$ 独立且均值为零，则

把它改写为

就得到 Proposition 2.7.1 的精确版本。

(e) Centering 的精确版本（Lemma 2.7.8）：

通过修改 Proposition 2.6.1 的证明，证明 Proposition 2.8.1 中性质 (i)-(iii) 的等价性。

下面给出一个一般框架，它覆盖了我们目前见过的大多数范数。设 $\psi:[0,\infty)\to[0,\infty)$ 是非递减、凸函数，且 $\psi(0)=0$。随机变量 $X$ 的 Orlicz 范数定义为

(a) 验证：在同一个概率空间上所有满足 $\|X\|_\psi<\infty$ 的随机变量集合中，这确实定义了一个范数。

(b) 解释为什么以下都是 Orlicz 范数的例子：任意 $p\in[1,\infty)$ 的 $L^p$ 范数、次高斯范数 $\|X\|_{\psi_2}$、以及次指数范数 $\|X\|_{\psi_1}$。

考虑尾部以 $\exp(-ct^\alpha)$ 或更快速度衰减的分布，其中 $\alpha\in(0,\infty)$ 是固定参数。当 $\alpha=2$ 时，这些分布是次高斯分布；当 $\alpha=1$ 时，它们是次指数分布。针对这样的分布，陈述并证明 Proposition 2.8.1(i)-(iii) 的一个版本，并定义 $\psi_\alpha$ 范数。

次高斯分布的许多性质经过适当修改后可推广到次指数分布。请对次指数分布陈述并证明以下结论：

(a) Centering 的一个版本（Lemma 2.7.8），它已经在 (2.26) 中陈述。

(b) Maximal inequality 的一个版本（Exercise 2.39）。

(c) Convex dominance 的一个版本（Exercise 2.28）。

下面是像 Theorem 2.9.1 这样的结果的一种常见表述。设 $X_1,\ldots,X_N$ 是独立、均值为零的次指数随机变量。检查：对每个 $u\ge0$，都有

其中

证明 Theorem 2.7.5 的下面这个次指数版本。设 $X_1,\ldots,X_N$ 是独立、均值为零的次指数随机变量，且 $a=(a_1,\ldots,a_N)\in\mathbb{R}^N$。那么，对每个 $p\in[2,\infty)$，都有

其中 $K=\max_i\|X_i\|_{\psi_1}$，且 $C$ 是绝对常数。

(a) 设 $X$ 是均值为零的随机变量，且 $|X|\le K$ a.s.。证明 $X$ 的 MGF 满足下面的界：

只要 $|\lambda|<3/K$。

(b) 用指数矩方法推出 Theorem 2.9.5。

我们来证明 Bernstein 不等式（Theorem 2.9.5）的下面这个强化版本。设 $X_1,\ldots,X_N$ 是独立、均值为零的随机变量，并且对所有 $i$ 都满足 $|X_i|\le K$。那么，对每个 $t\ge0$，都有

其中

按以下步骤证明：

(a) 设 $X$ 是均值为零且满足 $|X|\le K$ 的随机变量。证明对任意 $\lambda>0$，$X$ 的 MGF 满足

(b) 使用指数矩方法推出 (2.36)。

(c) 检查在小偏差范围中，也就是 $u=Kt/\sigma^2\approx0$ 时，有 $h(u)\approx u^2/2$。因此 Bennett 不等式给出近似 Gaussian 的尾界 $\exp(-t^2/\sigma^2)$，差一个绝对常数因子。

(d) 检查总有

因此在大偏差范围中，Bennett 不等式给出 Poisson 型尾界

类似于 Exercise 2.13。

证明思路

先把乘积事件转成指数变量之和的小偏差事件。下界使用事件 $\{X_i\ge1/2,\ \forall i\}$，它包含在 $\{Y_n\ge \mathbb EY_n\}$ 中；上界用指数矩方法处理 $\sum_i-\log X_i$。

完整证明

由于 $X_i\sim\operatorname{Unif}[0,1]$ 且相互独立，

若所有 $X_i\ge1/2$，则 $Y_n\ge2^{-n}$，因此

令 $Z_i=-\log X_i$。则 $Z_i$ 独立且服从参数为 $1$ 的指数分布，并且

对任意 $\lambda>0$，Markov 不等式给出

取 $\lambda=1/\log2-1$，括号中的常数约为 $0.942<0.95$。于是

证明思路

把“左边减右边”看成 $t$ 的函数，证明它单调下降到 $0$。这样每个有限 $t$ 处函数值都非负。

完整证明

记标准正态密度为 $f(t)=(2\pi)^{-1/2}e^{-t^2/2}$，并令

当 $t\to\infty$ 时，Gaussian tail 和 $\frac{t}{t^2+1}f(t)$ 都趋于 $0$，所以 $F(t)\to0$。下面求导。由 $f'(t)=-tf(t)$，

所以 $F$ 单调递减且极限为 $0$。因此对所有 $t>0$，$F(t)\ge0$，即

证明思路

把上尾积分写成标准正态密度 $f(t)$ 乘上一个修正因子。因为 $f'(x)=-xf(x)$，每次分部积分都会从尾积分中剥离一个 $1/t$、$1/t^3$、$1/t^5$ 等项。

完整证明

设

Mills ratio 是

第一次分部积分使用 $f(x)=-f'(x)/x$：

这已经说明 $R(t)=t^{-1}+O(t^{-3})$。第二次对余项做同样处理：

代回得到

余项为正，所以

继续递推。令 $I_m(t)=\int_t^\infty x^{-2m}f(x)\,dx$。同样分部积分得到

把这个递推代回 $I_0(t)$，得到

其中余项 $R_m(t)$ 的符号与下一项一致，因为它是正数 $I_{m+1}(t)$ 乘上显式符号。于是任意两个相邻部分和把真实 Mills ratio 夹住。特别地，取前三项就得到 (2.30)。

证明思路

两问都只用 $f'(x)=-xf(x)$。一阶矩直接积分，二阶矩分部积分后套 Gaussian tail 上界。

完整证明

对 $t>0$，

再计算二阶截断矩：

由 Proposition 2.1.2 的上界，$\int_t^\infty f(x)\,dx\le f(t)/t$。因此

证明思路

比较两个偶函数的 Taylor 展开即可。指数函数每个偶次项的系数都不小于 $\cosh$ 的对应系数。

完整证明

展开得到

对每个 $k\ge0$，有

所以 $1/(2k)!\le1/(2^kk!)$。逐项比较非负级数，得到 $\cosh x\le e^{x^2/2}$。

证明思路

这和 Hoeffding 的证明完全同型：指数化尾事件，套 Markov，再优化参数。

完整证明

对任意 $\lambda>0$，

标准正态的 MGF 为 $\mathbb E e^{\lambda g}=e^{\lambda^2/2}$，因此

右侧在 $\lambda=t$ 处最小，得到 $\mathbb P\{g\ge t\}\le e^{-t^2/2}$。

证明思路

小球事件是下尾事件，对 $e^{-\lambda\sum X_i}$ 使用 Markov。密度有界给出 Laplace transform 的统一控制。

完整证明

对 $\lambda>0$，

因为 $X_i$ 非负且密度 $f_i$ 满足 $f_i\le K$，

所以概率不超过 $e^{\lambda\varepsilon N}(K/\lambda)^N$。取 $\lambda=1/\varepsilon$，得到

证明思路

指数函数是凸函数，区间上凸函数位于端点弦线之下。取期望后，端点权重只由均值决定。

完整证明

对 $x\in[a,b]$，凸性给出

取 $X$ 的期望，得到

若 $Y$ 取值于 $\{a,b\}$ 且 $\mathbb EY=\mathbb EX$，则 $\mathbb P\{Y=b\}=(\mathbb EX-a)/(b-a)$，上式正是 $\mathbb E e^{\lambda Y}$。

证明思路

先平移缩放到均值为 $0$、区间长度为 $1$，再用 Exercise 2.8 化到两点分布。两点分布的 cumulant 二阶导数是 Bernoulli 方差，最多为 $1/4$。

完整证明

平移不会改变 $X-\mathbb EX$，缩放只把 $\lambda$ 改成 $\lambda(b-a)$，所以只需证明 $\mathbb EX=0$ 且 $b-a=1$ 的情形。由 Exercise 2.8，可进一步假设 $X$ 只取端点 $a,b$。

设 $K(\lambda)=\log\mathbb E e^{\lambda X}$。因为 $\mathbb EX=0$，$K(0)=K'(0)=0$。在指数倾斜分布下，

Taylor 公式给出

还原尺度，得到

证明思路

对中心化和使用 Chernoff bound；独立性分解 MGF；每项用 Hoeffding lemma 控制；最后优化 $\lambda$ 并对左右尾合并。

完整证明

令 $S=\sum_i(X_i-\mathbb EX_i)$。对 $\lambda>0$，

右侧对 $\lambda$ 最小化，取 $\lambda=4t/\sum_i(b_i-a_i)^2$，得到

把 $X_i$ 换成 $-X_i$ 得到左尾同样的界。合并左右尾即为 Theorem 2.2.6。

证明思路

左尾用负的指数参数。因为 $\lambda<0$ 时 $e^{\lambda x}$ 是递减函数，事件 $S_N\le t$ 会变成上尾事件。

完整证明

对 $\lambda<0$，

Bernoulli 和满足

令 $e^\lambda=t/\mu$，也就是 $\lambda=\log(t/\mu)\le0$，得到

证明思路

直接估计二项分布质量函数。组合数给出 $(N/t)^t$，剩下的 $(1-\mu/N)^{N-t}$ 用一个基础对数不等式下界为 $e^{-\mu}$。

完整证明

对整数 $t\in[\mu,N]$，

使用 $\binom Nt\ge(N/t)^t$，前两项给出 $(\mu/t)^t$。令 $x=\mu/N$。由于 $t\ge\mu$，有 $N-t\le N(1-x)$，且 $0\le x\le1$，于是

函数 $(1-x)\log(1-x)+x$ 在 $[0,1)$ 上非负，所以 $(1-x)^{N(1-x)}\ge e^{-Nx}=e^{-\mu}$。因此

证明思路

Poisson 的 MGF 与 Bernoulli 和的 Chernoff 上界有相同形式，因此右尾和左尾优化完全相同。点概率直接用 $t!\le t^t$。

完整证明

若 $X\sim\operatorname{Pois}(\mu)$，则

右尾中取 $\lambda>0$，Markov 给出

当 $t\ge\mu$ 时取 $e^\lambda=t/\mu$，得到 $e^{-\mu}(e\mu/t)^t$。左尾同理取 $\lambda<0$，当 $0<t\le\mu$ 时同样得到 $e^{-\mu}(e\mu/t)^t$。

小偏差形式由 Exercise 2.14 的数值不等式直接推出。最后，若 $t$ 是正整数，

因为 $t!\le t^t$。

证明思路

右尾从 Chernoff 精确指数化简；左尾使用负参数版本。关键只剩两个一元函数不等式。

完整证明

右尾由 Theorem 2.3.1 得到

直接求导可验证，对所有 $\delta\ge0$，

所以右尾不超过 $\exp[-\delta^2\mu/(2+\delta)]$。

当 $0\le\delta<1$ 时，左尾由 Exercise 2.11 得到

同样的微积分给出 $\delta+(1-\delta)\log(1-\delta)\ge\delta^2/2$，这强于所需界。$\delta=1$ 由极限得到，若 $\delta>1$，左尾事件为空。合并左右尾即得

证明思路

把 $e^{\lambda x}$ 在 $[0,1]$ 上用端点弦控制。这样每个 $X_i$ 的 MGF 都不超过同均值 Bernoulli 变量的 MGF。

完整证明

若 $X_i\in[0,1]$ 且 $\mathbb EX_i=p_i$，则对 $\lambda\in\mathbb R$，凸性给出

取期望得

这正是 $\operatorname{Ber}(p_i)$ 的 MGF 上界。由于 Chernoff、左尾和小偏差证明只用到了独立性和这个 MGF 控制，三种结论对独立 $[0,1]$ 变量原样成立。

证明思路

把分组数取为与 $t^2$ 同阶的整数，丢弃少量样本或允许最后一组不用。所有估计只损失绝对常数。

完整证明

若 $t$ 很小，例如 $t<4$，结论可通过调小指数常数平凡保证。下面设 $t\ge4$，并取

此时 $1\le B\asymp t^2$。因为 $t\le\sqrt N$，有 $B\le N/16$，所以 $m\ge N/(2B)$。使用前 $mB$ 个样本分成 $B$ 组，每组均值为 $Z_j$。Chebyshev 给出

于是坏组数被 $\operatorname{Binom}(B,1/8)$ 随机变量支配。Chernoff 或 Hoeffding 不等式给出坏组至少一半的概率不超过 $e^{-cB}\le e^{-c't^2}$。中位数落出区间只能在坏组至少一半时发生，证明完成。这里 $c'$ 与原定理中的绝对常数合并。

证明思路

选择两个均值相距 $\mu$ 的 Laplace 平移族。假设估计量在两个模型下都给出过强置信界，再用似然比比较把第二个模型的高概率事件转移到第一个模型下，最后得到两个互斥事件同时高概率发生的矛盾。

完整证明

设 $X_i\sim\operatorname{Lap}(0,1)$，$Y_i\sim\operatorname{Lap}(\mu,1)$ 独立。Laplace 密度满足

坐标独立，所以对任意可测 $B\subset\mathbb R^N$，

反设断言成立。Laplace 分布方差为绝对常数 $2$。令 $t=\mu\sqrt N/(2\sqrt2)$，则断言给出

且

由似然比比较，

选取足够大的绝对常数 $\mu$，可使上面两个失败概率之和小于 $1$。于是同一个 $\mathbf X$ 下，事件 $|\widehat\mu|<\mu/2$ 和 $|\widehat\mu-\mu|<\mu/2$ 同时发生的概率为正。但这两个严格事件由三角不等式互斥，矛盾。因此断言不成立。

证明思路

固定顶点度数是二项变量，Chernoff 控制一个顶点异常的概率。再对异常顶点个数取期望，用 Markov 控制异常比例。

完整证明

固定顶点 $v$，其度数 $D_v\sim\operatorname{Binom}(n-1,p)$，均值为 $d$。Chernoff 小偏差给出

其中 $c>0$ 为绝对常数。令 $Z$ 为异常顶点个数，则

选择 $C$ 足够大，使 $d\ge C$ 时 $2e^{-cd}\le10^{-4}$。于是 $\mathbb EZ\le10^{-4}n$。由 Markov 不等式，

因此至少以 $0.99$ 的概率，异常顶点不超过 $1\%$，也就是至少 $99\%$ 顶点的度数位于 $[0.9d,1.1d]$。

证明思路

上界用固定顶点二项尾界加并集界。下界把顶点分成两半，只看一半顶点到另一半的度数；这些度数独立，再用二项点概率下界和独立重复。

完整证明

审校注：原题/OCR 的字面条件只写了 $d\le c(\log n)^{0.99}$。若允许 $d=0$，则图没有边，$\Delta(G)=0$，题中正的下界不可能成立。因此下界证明必须在通常的非退化稀疏情形下理解，例如假设 $d\ge d_0>0$ 为绝对常数。上界不需要这个下界。

记 $L=A\log n/\log\log n$。对固定顶点，Chernoff 粗界给出

若 $A$ 足够大且 $c$ 足够小，则由 $d\le c(\log n)^{0.99}$ 可得 $(ed/L)^L\le n^{-3}$。并集界给出 $\Delta(G)\le L$ 的概率至少 $1-n^{-2}$，特别大于 $0.995$。

下界取 $L=a\log n/\log\log n$，其中 $a>0$ 足够小。把顶点分成两个大小至少 $n/3$ 的集合 $U,W$。对每个 $v\in U$，令 $D_v^W$ 为 $v$ 到 $W$ 的边数。变量 $D_v^W$ 在 $v\in U$ 上相互独立，且 $D_v^W\sim\operatorname{Binom}(|W|,p)$，均值与 $d$ 同阶；在 $d\ge d_0$ 时，这个均值也有绝对正下界。

由二项点概率下界，

在 $d\le c(\log n)^{0.99}$ 且 $a,c$ 足够小时，右侧至少为 $n^{-1/2}$（把常数留足即可）。于是期望个数

这些事件独立，所以没有任何一个发生的概率至多 $\exp(-c n^{1/2})$。因此以概率至少 $0.995$，存在顶点 $v$ 满足 $D_v^W\ge L$，从而 $\Delta(G)\ge L$。合并上下界并调整绝对常数，即得题设的 $0.99$ 概率结论。

证明思路

固定 $S,T$ 时，边数是 Bernoulli 和；Chernoff 给出指数为 $p|S||T|$ 的失败概率。条件 $|S||T|\ge Cn/p$ 让这个指数压过所有集合对的数量。

完整证明

固定互不相交的 $S,T$，令 $s=|S|,t=|T|$。则

Chernoff 小偏差给出

所有有序不交对 $(S,T)$ 的数量不超过 $3^n$，因为每个顶点有三种选择：进 $S$、进 $T$ 或都不进。若 $st\ge Cn/p$，则 $pst\ge Cn$。对所有满足条件的集合对取并集界，失败概率至多

选择 $C$ 足够大，使该值不超过 $2^{-n}$。补事件上对所有这样的 $S,T$ 同时有

证明思路

把每次运行是否正确记为 Bernoulli 变量。多数投票失败就是 Bernoulli 和低于其均值 $\varepsilon N$，直接套 Hoeffding。

完整证明

令 $Y_i$ 表示第 $i$ 次运行正确，则 $\mathbb EY_i=1/2+\varepsilon$。多数投票失败意味着

Hoeffding 不等式给出

若 $N\ge(2\varepsilon^2)^{-1}\log(1/\delta)$，右侧至多为 $\delta$。因此多数投票至少以 $1-\delta$ 的概率正确。

证明思路

偶对称性把积分化到正半轴；换元 $u=x^2/2$ 得到 Gamma 函数。渐近用 Stirling 公式。

完整证明

对 $p\ge1$，

令 $u=x^2/2$，即 $x=(2u)^{1/2}$，$dx=(2u)^{-1/2}du$，得到

令 $z=(p-1)/2$。由 Stirling 公式 $\Gamma(z+1)=\sqrt{2\pi z}(z/e)^z(1+o(1))$，取 $p$ 次方根后，多项式因子贡献趋于 $1$，于是

证明思路

在 $\lambda=0$ 附近比较一阶项。正参数给出 $\mathbb EX\le0$，负参数给出 $\mathbb EX\ge0$。

完整证明

若对所有 $\lambda\in\mathbb R$，

则对 $\lambda>0$，

令 $\lambda\downarrow0$ 得 $\mathbb EX\le0$。对 $\lambda<0$ 作同样处理，或者令 $\lambda=-s$ 后让 $s\downarrow0$，得到 $\mathbb EX\ge0$。因此 $\mathbb EX=0$。

证明思路

全部从定义出发：求使 $\mathbb E\exp(X^2/K^2)\le2$ 成立的最小 $K$。

完整证明

若 $X=c$ a.s.，条件为 $e^{c^2/K^2}\le2$，故 $\|X\|_{\psi_2}=|c|/\sqrt{\log2}$。若 $|X|\le\|X\|_\infty$，则由单调性

Rademacher 变量满足 $X^2=1$，所以范数为 $1/\sqrt{\log2}$。

若 $X\sim N(0,\sigma^2)$，则对 $K^2>2\sigma^2$，

令该值等于 $2$，得 $1-2\sigma^2/K^2=1/4$，即 $K=\sigma\sqrt{8/3}$。

若 $X\sim\operatorname{Ber}(p)$，则 $X^2=X$，条件为

等号给出 $e^{1/K^2}=1+1/p$，故

证明思路

次高斯变量必须满足 Gaussian 型尾界 $2e^{-ct^2/K^2}$。只要某个分布的尾部比这个慢，就不可能次高斯。

完整证明

若 $X$ 是次高斯，则存在 $c,K>0$ 使

exponential、geometric、Gamma 和 chi-squared 的尾部至多是 $e^{-ct}$ 量级；Poisson 右尾是 Poisson/Chernoff 型，固定分布下也比 $e^{-ct^2}$ 慢。Cauchy 和 Pareto 的尾部是多项式量级。上述尾部都不能被某个 Gaussian 型 $e^{-ct^2}$ 在所有大 $t$ 上控制。因此这些分布都不是次高斯。

证明思路

正向用 Orlicz 定义和 Hölder/Jensen 的幂次缩放；反向在端点 $\lambda=1/K$ 处取值得到 Orlicz 控制。

完整证明

设 $K_0=\|X\|_{\psi_2}$，则 $\mathbb E e^{X^2/K_0^2}\le2$。若 $|\lambda|\le1/K_0$，记 $\alpha=\lambda^2K_0^2\in[0,1]$，则

这证明了正向。

反过来，若 (2.31) 对某个 $K$ 成立，取 $\lambda=1/K$ 得

用同样的幂次缩放，

所以 $\|X\|_{\psi_2}\le2K$。

证明思路

正向比较两个尾界：次高斯尾和 Gaussian tail 下界。反向直接把 Gaussian tail 上界传回 $X$。因子 $2$ 的必要性由非零常数变量给出。

完整证明

若 $X$ 次高斯，令 $K_0=\|X\|_{\psi_2}$。存在绝对常数 $c,C$ 使

选择足够大的绝对常数 $A$，可使对 $t\ge AK_0$ 有

对 $t<AK_0$，右侧是一个正的绝对常数量级；继续增大 $A$ 即可覆盖这一区间。因此 $|X|\preceq AK_0|g|$。

反过来，若 $|X|\preceq K|g|$，则

由尾部刻画，$X$ 是次高斯且 $\|X\|_{\psi_2}\le CK$。

若把定义中的因子 $2$ 换成 $1$，取 $X\equiv1$。它是次高斯，但不存在有限 $K$ 使 $1\le K|g|$ 在随机支配意义下成立；例如 $0<t<1$ 时左尾概率为 $1$，而 $\mathbb P\{K|g|\ge t\}<1$。

证明思路

凸支配到次高斯很直接：测试指数型凸函数。次高斯到凸支配可由尾支配和 layer-cake 表示推出，常数通过放大 Gaussian 尺度吸收。

完整证明

先设 $|X|\precsim K|g|$。取非负、凸、递增函数 $\Phi(u)=e^{u^2/L^2}$ 在 $u\ge0$ 上的截断平滑版本，再令截断趋于无穷，可得

取 $L=CK$ 足够大，右侧至多为 $2$，所以 $\|X\|_{\psi_2}\le CK$。

反过来，若 $X$ 次高斯，由 Exercise 2.27，$|X|\preceq K_0|g|$，其中 $K_0\le C\|X\|_{\psi_2}$。对任意非负凸递增 $\Phi$，可先令 $\Phi(0)=0$；常数项不影响比较。由 layer-cake 公式，

凸性和单调性给出 $2\Phi(u)\le\Phi(2u)$（在 $\Phi(0)=0$ 后成立）。因此

这就是 $|X|\precsim K|g|$，其中 $K\le C\|X\|_{\psi_2}$。

证明思路

有界中心化变量是次高斯变量，尺度由区间长度控制。把次高斯 Hoeffding 套到中心化和即可。

完整证明

若 $X_i\in[a_i,b_i]$，则由 Exercise 2.9 或有界变量的 Orlicz 控制，

把 Theorem 2.7.3 用于独立中心化变量 $X_i-\mathbb EX_i$，得到

这就是 Theorem 2.2.6 的形式，只是指数中的绝对常数可能与原来不同。

证明思路

先用独立性和单位方差算二阶矩，再用次高斯 Khintchine 控制四阶矩，最后对 $Z^2$ 使用 Paley-Zygmund。

完整证明

令 $Z=\sum_i a_iX_i$，$\sigma^2=\sum_i a_i^2$。由于 $X_i$ 独立、均值为零、方差为一，

由次高斯 Khintchine 或 Proposition 2.7.1 的矩形式，

从而 $\mathbb EZ^4\le CK^4\sigma^4$。对非负随机变量 $W=Z^2$ 用 Paley-Zygmund，

这等价于

证明思路

取平均系数 $a_i=1/N$。Hoeffding 型界迫使样本均值以高概率趋近 $0$；大数定律又让它趋近真实均值。

完整证明

令 $a_i=1/N$。假设存在 $c>0$ 使

对所有 $N,t$ 成立。固定任意 $t>0$，右侧随 $N\to\infty$ 趋于 $0$，所以样本均值依概率收敛到 $0$。另一方面，由大数定律，样本均值依概率收敛到 $\mathbb EX_1$。依概率极限唯一，因此 $\mathbb EX_1=0$。

证明思路

上界是 Orlicz 范数三角不等式。下界用矩刻画：条件化后由 Jensen 得到 $\|X+Y\|_{L^p}$ 同时控制 $\|X\|_{L^p}$ 和 $\|Y\|_{L^p}$。

完整证明

上界直接由三角不等式给出：

下界使用等价刻画

固定 $p\ge1$，由于 $y\mapsto|x+y|^p$ 是凸函数且 $\mathbb EY=0$，

再对 $X$ 取期望，得 $\|X+Y\|_{L^p}\ge\|X\|_{L^p}$。同理 $\|X+Y\|_{L^p}\ge\|Y\|_{L^p}$。取上确界可得

证明思路

上界是 Proposition 2.7.1。下界用 exact subgaussian norm：对 i.i.d. 中心化变量，和的 MGF 是单个 MGF 的 $N$ 次方，因此 exact subgaussian variance 对和精确按 $N$ 缩放。最后用 exact norm 与标准 $\psi_2$ norm 的等价性。

完整证明

上界由 Proposition 2.7.1 立即得到：

为证明下界，引入 Exercise 2.40 中的 exact subgaussian variance。对中心化变量 $Z$，记

设 $S_N=\sum_{i=1}^NX_i$。若 $\sigma^2>\operatorname{Var}_G(X)$，则

所以 $\operatorname{Var}_G(S_N)\le N\operatorname{Var}_G(X)$。反过来，若 $\tau^2>\operatorname{Var}_G(S_N)$，则

两边取 $N$ 次方根，得到

因此 $\operatorname{Var}_G(X)\le\tau^2/N$。令 $\tau^2\downarrow\operatorname{Var}_G(S_N)$，得到 $\operatorname{Var}_G(S_N)\ge N\operatorname{Var}_G(X)$。于是

因为 $X$ 和 $S_N$ 都中心化，exact norm 满足 $\|Z\|_G^2=\operatorname{Var}_G(Z)$，所以

Exercise 2.40 证明 $\|Z\|_G\asymp\|Z\|_{\psi_2}$，常数为绝对常数。因此

这证明了 (a)。

对 (b)，令 $X_i=\operatorname{Ber}(p)-p$。则 $S_N-Np=\sum_iX_i$。先计算单个中心化 Bernoulli 的尺度。若 $p\le1/2$，则 $|X_i|\le1$ 给出上界；更精确地取 $K=C/\sqrt{\log(2/p)}$，可直接验证

当 $C$ 足够大时成立。下界由 $\mathbb P\{|X_i|\ge1/2\}\ge p$ 给出：若 $\mathbb E e^{X_i^2/K^2}\le2$，则 $p e^{1/(4K^2)}\le2$，所以 $K\ge c/\sqrt{\log(2/p)}$。当 $p>1/2$ 时，$\log(2/p)$ 为绝对常数量级，且 $X_i$ 有有界非退化波动，因此范数也是绝对常数量级。综上

代入 (a)，得到

证明思路

用越来越稀有、越来越大的对称尖峰变量。每个变量本身的 $\psi_2$ 范数同阶，但由于尖峰幅度超指数分离，任意有限和的尾部由最大的活跃尖峰主导。

完整证明

取 $b_i=4^i$。令 $\eta_i$ 是 Bernoulli 变量，$\mathbb P\{\eta_i=1\}=e^{-b_i^2}$；令 $\varepsilon_i$ 是独立 Rademacher 变量，并设

则 $\mathbb EX_i=0$，且

而若把常数缩小则指数矩爆炸。因此 $\|X_i\|_{\psi_2}\asymp1$。

设 $\|a\|_\infty\le1$，$S=\sum_{i=1}^Na_iX_i$。由于 $b_i=4^i$，任意一组活跃尖峰的总绝对值至多为最大活跃 $b_i$ 的绝对常数倍。因此若 $|S|\ge t$，必有某个 $i$ 满足 $\eta_i=1$ 且 $b_i\ge ct$。于是

所以 $\|S\|_{\psi_2}\le C$。缩放得到一般上界 $\|S\|_{\psi_2}\le C\|a\|_\infty$。

反向下界取 $j$ 使 $|a_j|=\|a\|_\infty$。条件化其它变量并用 Exercise 2.32 中的 Jensen/moment 下界，可得 $\|S\|_{\psi_2}\ge c|a_j|\|X_j\|_{\psi_2}\ge c\|a\|_\infty$。因此

取 $a_i=1$ 时，右侧为 $1$，而 $\left(\sum_i\|X_i\|_{\psi_2}^2\right)^{1/2}\asymp\sqrt N$，所以 Proposition 2.7.1 的不等式不能一般反向。

证明思路

先用矩插值 $\|X\|_{L^p}\le a^{1/p}b^{1-1/p}$，再用 $\psi_2$ 的矩刻画优化 $p$。紧性由两点变量给出。

完整证明

设 $\mathbb E|X|=a$ 且 $|X|\le b$。由插值或 Hölder，

令 $L=\log(2b/a)$。由矩刻画，

函数 $e^{-L/p}/\sqrt p$ 的最大值在 $p\asymp L$ 处，最大量级为 $1/\sqrt L$。因此

紧性取 $X=b$ 的概率为 $a/b$、$X=0$ 的概率为 $1-a/b$。此时

从等于 $2$ 解得 $K\asymp b/\sqrt{\log(2b/a)}$。

证明思路

先证明一个 $L^1,L^2,L^3$ 插值式。然后对线性组合 $Z$ 用 $L^2$ 的精确方差和 $L^3$ 的次高斯上界推出 $L^1$ 下界；最后由 $L^p$ 单调性扩展到 $[1,2]$。

完整证明

(a) 由 log-convexity，若 $1/2=(1-\theta)/1+\theta/3$，则 $\theta=3/4$，所以

(b) 令 $Z=\sum_i a_iX_i$，$\sigma=(\sum_i a_i^2)^{1/2}$。由独立、零均值、单位方差，$\|Z\|_{L^2}=\sigma$。由 Theorem 2.7.5 或次高斯矩界，

代入 (a)：

整理得 $\|Z\|_{L^1}\ge cK^{-3}\sigma$。上界由 Jensen/Cauchy 得 $\mathbb E|Z|\le\|Z\|_{L^2}=\sigma$。

(c) 对 $p\in[1,2]$，$L^p$ 范数随 $p$ 增大而增大，所以下界由 $L^1$ 给出，上界由 $L^2$ 给出：

证明思路

对上确界做 union bound。归一化让第 $k$ 项的尾概率变成 $(2k)^{-A}$，从而级数可求和。

完整证明

令 $K=\sup_k\|X_k\|_{\psi_2}$，并设

由次高斯尾界，

当 $t\ge CK$ 时，级数被 $C\exp(-c't^2/K^2)$ 控制；当 $t<CK$ 时可调大常数使尾界平凡成立。因此 $M$ 有次高斯尾，等价地

证明思路

上界用指数矩和 Jensen。独立情形的下界用 Gaussian tail 下界证明最大值超过 $(1-o(1))\sqrt{2\log N}$ 的概率趋于 $1$。

完整证明

(a) 对任意 $\lambda>0$，Jensen 与 union bound 给出

取对数并优化 $\lambda$，得到 $\mathbb E\max_i g_i\le\sqrt{2\log N}$。对绝对值，把 $g_i$ 和 $-g_i$ 视作 $2N$ 个 Gaussian，得到 $\mathbb E\max_i|g_i|\le\sqrt{2\log(2N)}$。

(b) 设 $u_N=(1-\varepsilon)\sqrt{2\log N}$。由 Gaussian tail 下界，

独立性给出

因此 $\max_i g_i\ge(1-\varepsilon)\sqrt{2\log N}$ 以高概率发生，期望下界同阶；令 $\varepsilon\downarrow0$ 得到渐近。绝对值版本同理，或由 $\max_i|g_i|\ge\max_i g_i$ 给下界、由 (a) 给上界。

证明思路

若尾概率 $p=\mathbb P\{|X|>t\}$ 不小，则取 $N\asymp1/p$ 个副本，最大值超过 $t$ 的概率为常数量级。最大值期望上界迫使 $t\lesssim K\sqrt{\log(1/p)}$，这就是 Gaussian 尾。

完整证明

设 $p(t)=\mathbb P\{|X|>t\}$。若 $p(t)>0$，取整数 $N\ge2$ 使 $1/N\le p(t)\le2/N$。则

于是

因为 $N\le2/p(t)$，得到

等价变形即

由尾部刻画，$X$ 是次高斯且 $\|X\|_{\psi_2}\le CK$。

证明思路

定义基于中心化 MGF。范数三角不等式用 Hölder；等价性用 Proposition 2.6.1；方差比较由 MGF 在零点二阶展开；独立和由 MGF 分解。

完整证明

(a) 齐次性来自替换 $\lambda$：$\operatorname{Var}_G(aX)=a^2\operatorname{Var}_G(X)$。非退化性由 $\|X\|_G=0$ 推出 $\operatorname{Var}(X)=0$ 且 $\mathbb EX=0$，所以 $X=0$ a.s.。三角不等式如下。设 $\sigma_X^2>\operatorname{Var}_G(X)$、$\sigma_Y^2>\operatorname{Var}_G(Y)$，并取 $p,q>1$，$1/p+1/q=1$。Hölder 给出

优化 $p,q$ 得 $\operatorname{Var}_G(X+Y)^{1/2}\le \operatorname{Var}_G(X)^{1/2}+\operatorname{Var}_G(Y)^{1/2}$，再与均值部分的三角不等式合并。

(b) Proposition 2.6.1 的 MGF 刻画给出 $\operatorname{Var}_G(X)^{1/2}\asymp\|X-\mathbb EX\|_{\psi_2}$；再用 $\|X\|_{\psi_2}\asymp\|X-\mathbb EX\|_{\psi_2}+|\mathbb EX|$，得到 $\|X\|_G\asymp\|X\|_{\psi_2}$。

(c) 若 $\mathbb Ee^{\lambda(X-\mathbb EX)}\le e^{\sigma^2\lambda^2/2}$，比较 $\lambda=0$ 处二阶项得 $\operatorname{Var}(X)\le\sigma^2$。取下确界得 $\operatorname{Var}(X)\le\operatorname{Var}_G(X)$，从而 $\|X\|_{L^2}\le\|X\|_G$。正态变量的 MGF 精确等于 $e^{\operatorname{Var}(X)\lambda^2/2}$，故取等号。

(d) 若 $X_i$ 独立且中心化，则

所以 $\operatorname{Var}_G(\sum_iX_i)\le\sum_i\operatorname{Var}_G(X_i)$。均值为零时这就是 $\|\sum_iX_i\|_G^2\le\sum_i\|X_i\|_G^2$。

(e) 中心化后均值项消失，且 $\operatorname{Var}_G(X-\mathbb EX)=\operatorname{Var}_G(X)$，所以 $\|X-\mathbb EX\|_G\le\|X\|_G$。

证明思路

完全平行于次高斯证明，只把 $\sqrt p$ 换成 $p$，把 $e^{-ct^2}$ 换成 $e^{-ct}$。

完整证明

若 $\mathbb P\{|X|>t\}\le2e^{-ct/K}$，则由尾积分公式，

所以 $\|X\|_{L^p}\le CKp$。若 moment growth 成立，则展开指数级数，取足够大的 $C$ 得

这就是 $\psi_1$ Orlicz 控制。最后若 $\mathbb E e^{|X|/K}\le2$，Markov 给出

三种性质互相推出，参数只差绝对常数。

证明思路

齐次性直接来自定义；三角不等式用 $\psi$ 的凸性；非退化性需要 $\psi(t)>0$ 对 $t>0$。例子由具体 $\psi$ 代入。

完整证明

设 $\|X\|_\psi\le K$、$\|Y\|_\psi\le L$。则由凸性和 $|X+Y|\le|X|+|Y|$，

取期望得 $\|X+Y\|_\psi\le K+L$，再取下确界得到三角不等式。齐次性由

立即得到。若 $\|X\|_\psi=0$，则对任意 $K>0$ 有 $\mathbb E\psi(|X|/K)\le1$；令 $K\downarrow0$ 并用 $\psi(t)>0$，得到 $X=0$ a.s.。

取 $\psi(t)=t^p$ 时，该范数与 $L^p$ 范数一致。取 $\psi(t)=e^{t^2}-1$ 得次高斯范数的等价版本；取 $\psi(t)=e^t-1$ 得次指数范数的等价版本。

证明思路

把次高斯的 $2$ 和次指数的 $1$ 统一成一般幂次 $\alpha$。证明仍然是 tail 积分、指数级数和 Markov 三步。注意：这里统一的是 tail、moment、Orlicz 三种刻画，不把普通 MGF $\mathbb E e^{\lambda X}$ 当作所有 $\alpha$ 下的统一条件；相关大偏差尺度见 概率论背景补充附录。

完整证明

定义

等价刻画为：存在绝对常数调整后的 $K$，使

以及

tail 到 moment：用

并换元 $u=ct^\alpha/K^\alpha$。moment 到 Orlicz：展开 $\exp(|X|^\alpha/(CK)^\alpha)$ 的级数并用 $\Gamma(m+1)$ 量级吸收。Orlicz 到 tail：直接对 $\exp(|X|^\alpha/K^\alpha)$ 用 Markov。$\alpha=2$ 和 $\alpha=1$ 分别回到次高斯和次指数。

如果想把 $\exp(-ct^\alpha)$ 尾部和 log MGF 的凸共轭联系起来，必须区分 $\lambda\to0$ 与 $|\lambda|\to\infty$ 两个尺度；这部分已经单独放入附录，避免把高级旁注混进本题证明。

证明思路

把次高斯论证中的 $\sqrt{\log N}$ 换成 $\log N$，把 Gaussian 支配变量换成 exponential 型变量。

完整证明

(a) 中心化：由 Orlicz 范数三角不等式和 Jensen，

(b) 最大不等式：若 $K=\max_i\|X_i\|_{\psi_1}$，则 union bound 给出

这等价于 $\|\max_i|X_i|\|_{\psi_1}\le CK\log(2N)$。

(c) 凸支配：设 $E$ 为均值为绝对常数的指数变量。次指数尾界等价于 $|X|\preceq K E$。再用 Exercise 2.28 的 layer-cake/凸性放大论证，把近似尾支配转为凸支配：存在绝对常数 $C$ 使 $|X|\precsim CK E$。反向用 $\Phi(u)=e^{u/L}$ 的截断版本即可。

证明思路

从 `min(二次项, 一次项)` 尾界出发，选择 $t=C(\sigma\sqrt u+Ku)$，使两个分母项都至少为常数倍 $u$。

完整证明

由 Theorem 2.9.1，

令 $t=C_0(\sigma\sqrt u+Ku)$。则

选 $C_0$ 足够大，使 $c\min(C_0^2u,C_0u)\ge u$。于是

证明思路

先对线性组合应用 Bernstein 得到混合尾，再用尾积分公式计算 $L^p$。二次尾贡献 $\sqrt p\|a\|_2$，一次尾贡献 $p\|a\|_\infty$。

完整证明

令 $S=\sum_i a_iX_i$，$K=\max_i\|X_i\|_{\psi_1}$。由 Bernstein 不等式，

利用尾积分公式

把右侧分别用两个尾界控制。Gaussian 型部分给出 $CK\sqrt p\|a\|_2$，指数型部分给出 $CKp\|a\|_\infty$。合并即

证明思路

MGF 用 Taylor 展开，利用 $|X|^k\le K^{k-2}X^2$ 把高阶矩都压到二阶矩上。然后指数矩方法优化参数。

完整证明

因为 $\mathbb EX=0$，

由 $k!\ge2\cdot3^{k-2}$，当 $|\lambda|<3/K$ 时，

再用 $1+u\le e^u$，得到

对独立和 $S=\sum_iX_i$，令 $\sigma^2=\sum_i\mathbb EX_i^2$，则

Markov 给出 $\mathbb P\{S\ge t\}\le\exp[-\lambda t+g(\lambda)\sigma^2]$。取 $\lambda=t/(\sigma^2+Kt/3)$（它小于 $3/K$），得到右尾 Bernstein；对 $-S$ 重复并合并，得到 Theorem 2.9.5。

证明思路

先用一条二次插值不等式控制单个有界变量的 MGF；再对和分解 MGF 并精确优化 $\lambda$。最后分析 $h(u)$ 在 $0$ 附近和无穷远的行为。

完整证明

(a) 对 $|x|\le K$，凸性可验证

令 $x=X$ 并取期望，利用 $\mathbb EX=0$ 和 $1+u\le e^u$，得到

(b) 对 $S=\sum_iX_i$，独立性给出

Markov 不等式给出

优化条件为 $e^{\lambda K}=1+Kt/\sigma^2$。令 $u=Kt/\sigma^2$，代回得

对 $-S$ 重复并合并，得到 (2.36)。

(c) Taylor 展开给出 $h(u)=u^2/2+O(u^3)$，所以小偏差时指数为 $-ct^2/\sigma^2$，即 Gaussian 型。

(d) 当 $u\ge1$ 时，微积分可验证 $h(u)\ge\frac12u\log u$；当 $0<u<1$ 时右侧为负，结论平凡。因此大偏差时

加上双侧因子 $2$，得到题中 Poisson 型尾界。