精校翻译
本页覆盖第 2 章正文、Notes 与 Exercises 2.1-2.48；学习笔记页已加入关键定理完整证明、习题证明工作区和可用于并排阅读的跳转链接。
目录
| 原书部分 | 中文说明 | 页码 | 翻译 | 笔记 |
|---|---|---|---|---|
| Chapter 2 | 独立随机变量和的集中现象总览。 | PDF p.1 | 译文 | 笔记 |
| 2.1 Why concentration inequalities? | 从 Chebyshev、Gaussian tail 和 Berry-Esseen 说明为什么需要非渐近集中界。 | PDF p.1-4 | 译文 | 笔记 |
| 2.2 Hoeffding inequality | Rademacher 和有界独立变量的 Hoeffding 不等式。 | PDF p.4-6 | 译文 | 笔记 |
| 2.3 Chernoff inequality | Bernoulli 和的 Chernoff 上尾、下尾与小偏差形式。 | PDF p.6-8 | 译文 | 笔记 |
| 2.4 Median-of-means | 用中位数-均值估计处理有限方差均值估计。 | PDF p.8-10 | 译文 | 笔记 |
| 2.5 Degrees of random graphs | 用 Chernoff 和并集界控制随机图顶点度。 | PDF p.10-11 | 译文 | 笔记 |
| 2.6 Subgaussian distributions | 次高斯分布的尾、矩母函数和矩增长等价刻画。 | PDF p.11-14 | 译文 | 笔记 |
| 2.6.1 The subgaussian norm | 次高斯范数及其基本用法。 | PDF p.14-15 | 译文 | 笔记 |
| 2.7 Subgaussian Hoeffding and Khintchine | 次高斯独立和、Khintchine 不等式、最大值和中心化。 | PDF p.15-19 | 译文 | 笔记 |
| 2.8 Subexponential distributions | 次指数变量的性质、范数和与次高斯平方的关系。 | PDF p.19-23 | 译文 | 笔记 |
| 2.9 Bernstein inequality | 用次指数控制独立和的 Bernstein 型尾界。 | PDF p.23-25 | 译文 | 笔记 |
| 2.10 Notes | 集中不等式、均值估计、随机图和 Orlicz 范数的参考线索。 | PDF p.25 | 译文 | 笔记 |
| Exercises 2.1-2.48 | Mills ratio、小球概率、Le Cam、随机图、随机支配、Orlicz 与 Bennett。 | PDF p.26-34 | 译文 | 证明 |
第 2 章：独立随机变量和的集中现象
本章进入集中不等式的广阔世界。我们先在第 2.1 节解释为什么需要集中不等式，然后介绍若干核心结果：Hoeffding 不等式、第 2.3 节的 Chernoff 不等式、第 2.9 节的 Bernstein 不等式，以及第 2.7 节的 Khintchine 不等式。
本章还会引入两类重要分布：次高斯分布和次指数分布。它们是高维概率及其应用中许多结果的“自然栖息地”。
本章给出集中不等式的两个应用：第 2.4 节的稳健均值估计，以及第 2.5 节的随机图度数。更多应用会在后续章节出现。
章末习题构成了一条补充路线，覆盖 Mills ratio、小球概率、Le Cam 二点法、随机图的 expander mixing lemma、随机支配、Orlicz 范数、Bennett 不等式等主题。
2.1 为什么需要集中不等式？
集中不等式刻画随机变量 $X$ 偏离其均值 $\mathbb EX=\mu$ 的概率。它们通常给出 $X-\mu$ 的双侧尾界，例如：
$$ \mathbb P\{|X-\mu|>t\} \le \text{something small}. $$
最简单的集中不等式是 Chebyshev 不等式（Corollary 1.6.3）。它非常一般，但经常太弱。我们用二项分布的例子来说明这一点。
抛一枚公平硬币 $N$ 次。得到至少 $\frac34N$ 次正面的概率是多少？
令 $S_N$ 表示正面次数。那么 $S_N$ 服从二项分布 $S_N\sim\operatorname{Binom}(N,1/2)$，因此
$$ \mathbb E S_N=\frac N2, \qquad \operatorname{Var}(S_N)=\frac N4. $$
Chebyshev 不等式把得到至少 $\frac34N$ 次正面的概率界定为
$$ \mathbb P\left\{S_N\ge \frac34N\right\} \le \mathbb P\left\{\left|S_N-\frac N2\right|\ge \frac N4\right\} \le \frac4N. \tag{2.1} $$
所以，这个概率至少以 $N$ 的线性速度收敛到零。
这是正确的衰减速度吗？还是应该期待更快的收敛？我们用中心极限定理重新看同一个问题。为此，把 $S_N$ 表示为独立随机变量之和：
$$ S_N=\sum_{i=1}^N X_i, $$
其中 $X_i$ 是参数为 $1/2$ 的独立 Bernoulli 随机变量，也就是“第 $i$ 次抛掷为正面”的指标。De Moivre-Laplace 中心极限定理 (1.25) 说明，标准化后的正面次数
$$ Z_N=\frac{S_N-N/2}{\sqrt{N/4}} $$
的分布收敛到标准正态分布 $N(0,1)$。因此，对大的 $N$，我们应当预期
$$ \mathbb P\left\{S_N\ge \frac34N\right\} = \mathbb P\left\{Z_N\ge \sqrt{N/4}\right\} \approx \mathbb P\left\{g\ge \sqrt{N/4}\right\}, \tag{2.2} $$
其中 $g\sim N(0,1)$。
遗憾的是，一般 $t$ 下的 Gaussian tail $\mathbb P\{g\ge t\}$ 无法用初等函数解析计算。它属于无法由初等函数表达的“特殊函数”之一。不过，Gaussian tail 有精确的近似。
设 $g\sim N(0,1)$。则对所有 $t>0$，都有
$$ \frac{t}{t^2+1}\cdot\frac1{\sqrt{2\pi}}e^{-t^2/2} \le \mathbb P\{g\ge t\} \le \frac1t\cdot\frac1{\sqrt{2\pi}}e^{-t^2/2}. $$特别地，对 $t\ge1$，尾概率可由密度控制：
$$ \mathbb P\{g\ge t\} \le \frac1{\sqrt{2\pi}}e^{-t^2/2}. \tag{2.3} $$ 查看学习笔记完整证明为得到尾概率的上界，先写出
$$ \mathbb P\{g\ge t\} = \frac1{\sqrt{2\pi}} \int_t^\infty e^{-x^2/2}\,dx. $$作变量替换 $x=t+y$。于是
$$ \mathbb P\{g\ge t\} = \frac1{\sqrt{2\pi}} \int_0^\infty e^{-t^2/2}e^{-ty}e^{-y^2/2}\,dy \le \frac1{\sqrt{2\pi}}e^{-t^2/2} \int_0^\infty e^{-ty}\,dy. $$这里用到了 $e^{-y^2/2}\le1$。最后一个积分等于 $1/t$，因此得到所需的尾概率上界。下界留到 Exercise 2.2 证明。
查看学习笔记完整证明Proposition 2.1.2 对多数用途已经足够。如果你需要更精确的近似，可以查看 Exercise 2.3。
查看学习笔记完整证明回到 (2.2)，我们应当预期“至少 $\frac34N$ 次正面”的概率可被下面这个量控制：
$$ \frac1{\sqrt{2\pi}}e^{-N/8}. \tag{2.4} $$
这个量随 $N$ 指数快地衰减到零，远好于 Chebyshev 不等式给出的线性衰减 (2.1)。
然而，界 (2.4) 并不能从中心极限定理严格推出。尽管 (2.2) 中的正态近似是有效的，但近似误差衰减得太慢。下面的中心极限定理定量版本可以看出这一点。
在 Theorem 1.7.3 的设定下，对每个 $N\in\mathbb N$ 和每个 $t\in\mathbb R$，都有
$$ \left| \mathbb P\{Z_N\ge t\} - \mathbb P\{g\ge t\} \right| \le \frac{\rho}{\sqrt N}, $$其中 $g\sim N(0,1)$，并且 $\rho=\mathbb E|X_1-\mu|^3/\sigma^3$。
所以，(2.2) 中的近似误差阶数是 $1/\sqrt N$，这会破坏我们希望得到的指数衰减 (2.4)。
中心极限定理中的近似误差能否改进？一般来说，不能。对偶数 $N$，恰好一半抛掷为正面的概率等于
$$ \mathbb P\{S_N=N/2\} = 2^{-N}\binom{N}{N/2} \approx \sqrt{\frac2{\pi N}}. $$
最后一个估计来自 Stirling 近似（Lemma 1.7.7）。请自行检查。 查看学习笔记证明 因此
$$ \mathbb P\{Z_N=0\} \approx \sqrt{\frac2{\pi N}}, \qquad \text{while} \qquad \mathbb P\{g=0\}=0. $$
最后一个等式成立，是因为正态分布是连续分布。因此，近似误差必须至少是 $1/\sqrt N$ 阶。
总之，中心极限定理把 $S_N=X_1+\cdots+X_N$ 近似为正态分布，而正态分布以轻尾、指数衰减尾部著称。但近似误差衰减太慢，阻碍了我们证明 $S_N$ 也具有这样的轻尾。为解决这个问题，我们将发展一种绕过中心极限定理的集中方法。
2.2 Hoeffding 不等式
我们从独立 Rademacher 随机变量和的一个简单集中不等式开始。随机变量 $X$ 称为 Rademacher 随机变量，是指
$$ \mathbb P\{X=-1\} = \mathbb P\{X=1\} = \frac12. $$
设 $X_1,\ldots,X_N$ 是独立 Rademacher 随机变量，$a=(a_1,\ldots,a_N)\in\mathbb R^N$ 固定。则对任意 $t\ge0$，都有
$$ \mathbb P\left\{\sum_{i=1}^N a_iX_i\ge t\right\} \le \exp\left(-\frac{t^2}{2\|a\|_2^2}\right). $$ 查看学习笔记完整证明这个论证可以称为指数矩方法。
回忆我们如何证明 Chebyshev 不等式（Corollary 1.6.3）：对两边平方，然后应用 Markov 不等式。这里做类似的事情，只是不再平方，而是乘以一个固定参数 $\lambda\ge0$（稍后选择其具体值）并取指数。于是
$$ \begin{aligned} \mathbb P\left\{\sum_{i=1}^N a_iX_i\ge t\right\} &= \mathbb P\left\{ \exp\left(\lambda\sum_{i=1}^N a_iX_i\right) \ge \exp(\lambda t) \right\} \\ &\le e^{-\lambda t} \mathbb E\exp\left(\lambda\sum_{i=1}^N a_iX_i\right). \end{aligned} \tag{2.5} $$最后一步使用了 Markov 不等式（Proposition 1.6.2）。
现在问题化为控制和 $\sum_{i=1}^N a_iX_i$ 的矩母函数。基础概率论告诉我们，由独立性可知，和的矩母函数等于各项矩母函数之积。因此
$$ \mathbb E\exp\left(\lambda\sum_{i=1}^N a_iX_i\right) = \prod_{i=1}^N \mathbb E\exp(\lambda a_iX_i). \tag{2.6} $$固定 $i$。由于 $X_i$ 以相同概率 $1/2$ 取值 $-1$ 和 $1$，我们有
$$ \mathbb E\exp(\lambda a_iX_i) = \frac12\exp(\lambda a_i) + \frac12\exp(-\lambda a_i) = \cosh(\lambda a_i). $$现在使用数值不等式
$$ \cosh(x)\le \exp(x^2/2) \quad\text{for all }x\in\mathbb R, \tag{2.7} $$它可由比较两边 Taylor 展开来验证（Exercise 2.5）。于是
查看学习笔记完整证明 $$ \mathbb E\exp(\lambda a_iX_i) \le \exp(\lambda^2 a_i^2/2). $$代回 (2.6)，再代回 (2.5)，得到
$$ \begin{aligned} \mathbb P\left\{\sum_{i=1}^N a_iX_i\ge t\right\} &\le e^{-\lambda t} \prod_{i=1}^N \exp(\lambda^2 a_i^2/2) \\ &= \exp\left( -\lambda t+\frac{\lambda^2}{2}\sum_{i=1}^N a_i^2 \right) \\ &= \exp\left( -\lambda t+\frac{\lambda^2}{2}\|a\|_2^2 \right). \end{aligned} \tag{2.8} $$这个界对任意 $\lambda\ge0$ 都成立。选择使 (2.8) 最小的 $\lambda$，即 $\lambda=t/\|a\|_2^2$，最小值为 $\exp(-t^2/(2\|a\|_2^2))$。请自行检查。Hoeffding 不等式得证。
查看学习笔记完整证明Hoeffding 不等式可以看作中心极限定理的集中版本。在归一化 $\|a\|_2=1$ 下，它给出指数轻尾 $e^{-t^2/2}$，几乎匹配 (2.3) 中的标准正态尾。
不同于概率论中的经典极限定理，Hoeffding 不等式是非渐近的：它对所有固定 $N$ 成立，而不只是当 $N\to\infty$ 时成立。后面会看到，非渐近结果对数据科学应用很有吸引力，因为其中 $N$ 往往对应样本量。
使用 Hoeffding 不等式，我们现在可以回到 Question 2.1.1，并界定公平硬币抛掷 $N$ 次中至少 $\frac34N$ 次正面的概率。注意，如果 $Y\sim\operatorname{Ber}(1/2)$，那么 $2Y-1$ 是 Rademacher 随机变量。由于正面次数 $S_N$ 是 $N$ 个独立 $\operatorname{Ber}(1/2)$ 变量之和，$2S_N-N$ 是 $N$ 个独立 Rademacher 随机变量之和。因此
$$ \begin{aligned} \mathbb P\left\{\text{at least }\frac34N\text{ heads}\right\} &= \mathbb P\left\{S_N\ge \frac34N\right\} \\ &= \mathbb P\left\{2S_N-N\ge \frac N2\right\} \\ &\le \exp(-N/8). \end{aligned} $$换句话说，该概率关于抛掷次数是指数小的。我们得到了一个严格界，并且它相当接近启发式猜测 (2.4)。
我们可以很容易把 Hoeffding 不等式推广到双侧尾概率 $\mathbb P\{|S_N|\ge t\}$，其中
$$ S_N=\sum_{i=1}^N a_iX_i. $$
为此，把事件 $|S_N|\ge t$ 表示为两个事件的并：$S_N\ge t$ 和 $-S_N\ge t$。并集界给出
$$ \mathbb P\{|S_N|\ge t\} \le \mathbb P\{S_N\ge t\} + \mathbb P\{-S_N\ge t\}. $$
分别对随机变量 $X_i$ 和 $-X_i$ 应用 Hoeffding 不等式，只需付出一个因子 $2$，就得到双侧尾界。
设 $X_1,\ldots,X_N$ 是独立 Rademacher 随机变量，且 $a=(a_1,\ldots,a_N)\in\mathbb R^N$。则对任意 $t>0$，都有
$$ \mathbb P\left\{ \left|\sum_{i=1}^N a_iX_i\right| \ge t \right\} \le 2\exp\left(-\frac{t^2}{2\|a\|_2^2}\right). $$我们用来证明 Hoeffding 不等式的指数矩方法相当灵活。它的适用范围远超 Rademacher 分布这个典型例子。例如，在 Exercise 2.10 中，你将证明下面这个针对一般有界随机变量的 Hoeffding 不等式扩展。
设 $X_1,\ldots,X_N$ 是独立随机变量，并且每个 $i$ 都满足 $X_i\in[a_i,b_i]$。则对任意 $t>0$，都有
$$ \mathbb P\left\{ \sum_{i=1}^N (X_i-\mathbb EX_i)\ge t \right\} \le \exp\left( -\frac{2t^2}{\sum_{i=1}^N(b_i-a_i)^2} \right). $$ 查看学习笔记完整证明2.3 Chernoff 不等式
Hoeffding 不等式对 Rademacher 随机变量相当尖锐，但对一般有界随机变量可能过于保守。例如，当 Bernoulli 随机变量 $X_i$ 的均值 $p_i$ 很小时，它们的和会近似 Poisson 分布（Theorem 1.7.6）。Hoeffding 不等式（Theorem 2.2.6）没有利用小的 $p_i$，因此给出的 Gaussian 界会远离真实的 Poisson tail。下面证明一个能感知 $p_i$ 大小的不等式。
设 $X_i$ 是独立 Bernoulli 随机变量，参数为 $p_i$。考虑它们的和
$$ S_N=\sum_{i=1}^N X_i, $$并记其均值为 $\mu=\mathbb ES_N$。那么
$$ \mathbb P\{S_N\ge t\} \le e^{-\mu}\left(\frac{e\mu}{t}\right)^t \quad\text{for any }t\ge\mu. $$ 查看学习笔记完整证明我们使用和 Hoeffding 不等式（Theorem 2.2.1）证明中相同的指数矩方法。和前面一样，把不等式 $S_N\ge t$ 乘以 $\lambda\ge0$，取指数，再应用 Markov 不等式和独立性，得到
$$ \mathbb P\{S_N\ge t\} \le e^{-\lambda t} \prod_{i=1}^N \mathbb E\exp(\lambda X_i). \tag{2.9} $$剩下要界定每个 Bernoulli 随机变量 $X_i$ 的矩母函数。由于它以概率 $p_i$ 取值 $1$，以概率 $1-p_i$ 取值 $0$，所以
$$ \mathbb E\exp(\lambda X_i) = e^\lambda p_i+(1-p_i) = 1+(e^\lambda-1)p_i \le \exp\left[(e^\lambda-1)p_i\right]. $$最后一步使用了 $1+x\le e^x$。因此
$$ \prod_{i=1}^N\mathbb E\exp(\lambda X_i) \le \exp\left[(e^\lambda-1)\sum_{i=1}^N p_i\right] = \exp\left[(e^\lambda-1)\mu\right]. $$代回 (2.9)，得到
$$ \mathbb P\{S_N\ge t\} \le e^{-\lambda t}\exp\left[(e^\lambda-1)\mu\right] = \exp\left[-\lambda t+(e^\lambda-1)\mu\right]. $$这个界对任意 $\lambda>0$ 成立。右侧表达式在 $\lambda=\ln(t/\mu)$ 处取得最小值（请检查），而由假设 $t\ge\mu$ 可知这个 $\lambda$ 非负。把该值代入并化简，即得 Chernoff 不等式。
查看学习笔记完整证明稍微修改 Chernoff 不等式的证明，也能得到左尾界：
$$ \mathbb P\{S_N\le t\} \le e^{-\mu}\left(\frac{e\mu}{t}\right)^t \quad\text{for every }0<t\le\mu. $$你将在 Exercise 2.11 中证明这个界。
Chernoff 不等式中的表达式 $e^{-\mu}(e\mu/t)^t$ 是否显得晦涩？想想当 $p_i$ 都很小时会发生什么。Poisson 极限定理（Theorem 1.7.6）提示 $S_N\approx\operatorname{Pois}(\mu)$。像 (1.27) 那样使用 Stirling 近似，我们预期
$$ \mathbb P\{S_N=t\} \approx \frac{e^{-\mu}}{\sqrt{2\pi t}} \left(\frac{e\mu}{t}\right)^t \quad\text{for every fixed integer }t>0. $$Chernoff 不等式给出类似结论，但它是严格且非渐近的。它本质上用尾部中的一个点概率 $\mathbb P\{S_N=t\}$ 控制整个尾概率 $\mathbb P\{S_N\ge t\}$。
Poisson tails 比 Gaussian 更重：它们按 $t^{-t}=e^{-t\log t}$ 衰减；当 $t$ 很大时，这比 $e^{-t^2}$ 更慢。幸运的是，这只发生在 $t$ 远大于均值 $\mu$ 的情形。对小偏差，Poisson tail 看起来类似 Gaussian tail。
在 Theorem 2.3.1 的设定下，
$$ \mathbb P\{|S_N-\mu|\ge \delta\mu\} \le 2\exp\left(-\frac{\delta^2\mu}{3}\right) \quad\text{for every }0\le\delta\le1. $$ 查看学习笔记完整证明在 Theorem 2.3.1 中取 $t=(1+\delta)\mu$ 并化简，得到
$$ \mathbb P\{S_N\ge(1+\delta)\mu\} \le \exp\left[ -\mu\left((1+\delta)\ln(1+\delta)-\delta\right) \right]. \tag{2.10} $$现在把指数中的表达式展开为 Taylor 级数：
$$ (1+\delta)\ln(1+\delta)-\delta = \frac{\delta^2}{2} - \frac{\delta^3}{2\cdot3} + \frac{\delta^4}{3\cdot4} - \frac{\delta^5}{4\cdot5} +\cdots \ge \frac{\delta^2}{3}. $$检查最后一个界时，可以从两边减去 $\delta^2/3$；这样得到一个符号交替且项递减的级数。把该界代入 (2.10)，得到
$$ \mathbb P\{S_N\ge(1+\delta)\mu\} \le \exp\left(-\frac{\delta^2\mu}{3}\right). $$左尾 $\mathbb P\{S_N\le(1-\delta)\mu\}$ 可以类似地用 Remark 2.3.2 控制。请尝试推导；你会得到更好的界 $\exp(-\delta^2\mu/2)$。最后用并集界合并左右两侧，证明完成。
查看学习笔记：左尾推导与小偏差合并为了在 Corollary 2.3.4 中看出 Gaussian tail，可以像中心极限定理那样粗略归一化 $S_N$。令 $Z_N=(S_N-\mu)/\sqrt\mu$，则 Corollary 2.3.4 的结论可改写为
$$ \mathbb P\{|Z_N|\ge t\} \le 2\exp(-t^2/3) \quad\text{for every }0\le t\le\sqrt\mu. $$
图 2.1 展示了分布 $\operatorname{Binom}(N,\mu/N)$ 在 $N=200$、$\mu=10$ 时的概率质量函数。靠近均值 $\mu$ 时，钟形曲线反映 Gaussian 行为。远离均值向右时，较慢的衰减反映 Poisson 行为。这两个区域分别对应中心极限定理和 Poisson 极限定理。
2.4 应用：均值的中位数估计量
数据科学中的一个基础问题，是从样本中学习未知分布；例如，从 $N$ 个人的调查中推断一个国家的收入分布。
最基本的任务是估计均值。设 $X$ 是均值为 $\mu$、方差为 $\sigma^2$ 的随机变量，它代表总体；设 $X_1,\ldots,X_N$ 是 $X$ 的独立拷贝，它们代表样本。我们希望找到一个估计量 $\widehat\mu=\widehat\mu(X_1,\ldots,X_N)$，使得 $\widehat\mu\approx\mu$ 以高概率成立。
最简单、最常用的均值估计量是样本均值
$$ \widehat\mu := \frac1N\sum_{i=1}^N X_i. \tag{2.11} $$
这个估计量的期望和方差为
$$ \mathbb E\widehat\mu=\mu, \qquad \operatorname{Var}(\widehat\mu) = \frac1{N^2}\sum_{i=1}^N\operatorname{Var}(X_i) = \frac{\sigma^2}{N}. \tag{2.12} $$
于是 Chebyshev 不等式给出
$$ \mathbb P\left\{ |\widehat\mu-\mu| \ge \frac{t\sigma}{\sqrt N} \right\} \le \frac1{t^2} \quad\text{for every }t>0. \tag{2.13} $$
例如，(2.13) 保证以至少 $99\%$ 的概率，误差不超过 $10\sigma/\sqrt N$；这已经是均值估计问题的一个可接受解。
但这个解最优吗？(2.13) 中的概率能不能比 $1/t^2$ 衰减得更快？对 Gaussian 分布，答案是肯定的。如果 $X\sim N(\mu,\sigma^2)$，那么 $\widehat\mu\sim N(\mu,\sigma^2/N)$，并且
$$ \frac{\widehat\mu-\mu}{\sigma/\sqrt N} \sim N(0,1). $$
对左右尾分别使用 Gaussian tail 界 (2.3)，得到
$$ \mathbb P\left\{ |\widehat\mu-\mu| \ge \frac{t\sigma}{\sqrt N} \right\} \le \sqrt{\frac2\pi}e^{-t^2/2} \quad\text{for every }t\ge1. $$
例如，误差以至少 $99\%$ 的概率不超过 $3\sigma/\sqrt N$。
人们可能会怀疑，如此强的 Gaussian tail 衰减需要类 Gaussian 假设。但出人意料的是：只要分布有有限方差，就存在一个具有 Gaussian tail 衰减的均值估计量。
设 $X$ 是均值为 $\mu$、方差为 $\sigma^2$ 的随机变量，$X_1,\ldots,X_N$ 是 $X$ 的独立拷贝。对任意 $0\le t\le\sqrt N$，存在一个估计量 $\widehat\mu=\widehat\mu(X_1,\ldots,X_N)$，满足
$$ \mathbb P\left\{ |\widehat\mu-\mu| \ge \frac{t\sigma}{\sqrt N} \right\} \le 2e^{-ct^2}, $$其中 $c>0$ 是绝对常数。
查看学习笔记完整证明我们将构造的估计量称为 median-of-means estimator。有限实数集 $\{x_1,\ldots,x_n\}$ 的一个中位数，记为
$$ \operatorname{Med}(x_1,\ldots,x_n), $$
它是一个值 $M$，使得至少一半的数满足 $x_i\le M$，并且至少一半的数满足 $x_i\ge M$。
虽然中位数不像均值那样有线性性等方便性质，但它有一个巨大优势：稳健性。如果把一个样本点 $x_i$ 推到无穷远，均值会变成无穷大；但中位数会保持不动，或者只是稍微移动，最多移到下一个点。为什么？ 查看学习笔记证明
为简单起见，假设 $N=BL$，其中 $B$ 和 $L$ 是整数。把样本 $X_1,\ldots,X_N$ 分成 $B$ 个长度为 $L$ 的分组；计算每组的样本均值，并取这些组均值的中位数：
$$ \mu_b = \frac1L\sum_{i=(b-1)L+1}^{bL}X_i, \qquad \widehat\mu = \operatorname{Med}(\mu_1,\ldots,\mu_B). $$和 (2.12) 中的论证一样，每个随机变量 $\mu_b$ 的期望为 $\mu$，方差为 $\sigma^2/L$。因此 Chebyshev 不等式给出
$$ \mathbb P\left\{ \mu_b\ge \mu+\frac{t\sigma}{\sqrt N} \right\} \le \frac{N}{t^2L} = \frac{B}{t^2} = \frac14, $$这里选择分组数 $B=t^2/4$。由中位数的定义，
$$ \begin{aligned} \mathbb P\left\{ \widehat\mu \ge \mu+\frac{t\sigma}{\sqrt N} \right\} \le \mathbb P\left\{ \text{at least half of }\mu_1,\ldots,\mu_B \text{ are }\ge \mu+\frac{t\sigma}{\sqrt N} \right\}. \end{aligned} $$我们面对的是 $B$ 个独立事件，每个发生概率至多为 $1/4$。由 Hoeffding 不等式（Theorem 2.2.6）可知，至少一半事件发生的概率被 $\exp(-c_0B)$ 控制，其中 $c_0>0$ 是绝对常数。请检查这一步。因此
查看学习笔记完整证明 $$ \mathbb P\left\{ \widehat\mu \ge \mu+\frac{t\sigma}{\sqrt N} \right\} \le \exp(-c_0B) = \exp(-c_0t^2/4). $$类似地，事件 $\widehat\mu\le\mu-t\sigma/\sqrt N$ 的概率也有相同界。合并这两个界即可完成证明。
不过，上面的论证有一个小小的不精确处。分组数 $B$ 必须是整数并且整除 $N$，而我们的选择 $B=t^2/4$ 由 $t$ 的假设只能保证 $0\le B\le N$。你将在 Exercise 2.16 中修正这个问题。
2.5 应用：随机图的度
我们把 Chernoff 不等式应用到一个经典组合对象：随机图。
最简单的随机图模型是 Erdős-Rényi 模型 $G(n,p)$。它在 $n$ 个顶点的集合上构造：任意一对不同顶点独立地以概率 $p$ 连接。图 2.2 展示了两个例子。Erdős-Rényi 模型常常作为大型真实网络最简单的随机模型。
图中一个顶点的度，指与它相连的边数。$G(n,p)$ 中每个顶点的期望度都等于
$$ (n-1)p=:d. $$
为什么？我们将证明：相对稠密的图，也就是满足 $d\gtrsim\log n$ 的图，以高概率几乎是正则的；这意味着所有顶点的度都近似等于 $d$。
存在一个绝对常数 $C$，使得下面结论成立。考虑随机图 $G\sim G(n,p)$，并假设其期望度满足 $d\ge C\log n$。那么，以至少 $0.99$ 的概率，下面事件发生：$G$ 的所有顶点的度都在 $0.9d$ 与 $1.1d$ 之间。
查看学习笔记完整证明论证结合了集中不等式和并集界。先固定图中的一个顶点 $i$。记 $i$ 的度为 $d_i$。它是 $n-1$ 个独立 $\operatorname{Ber}(p)$ 随机变量之和，也就是与 $i$ 关联的各条边的指标之和。应用 Chernoff 不等式（Corollary 2.3.4），得到
$$ \mathbb P\{|d_i-d|\ge 0.1d\} \le 2e^{-cd}. $$这个界对每个固定顶点 $i$ 成立。接下来，我们可以通过对所有 $n$ 个顶点使用并集界（Lemma 1.4.1）来“解除固定”的 $i$。于是
$$ \begin{aligned} \mathbb P\{\exists i\le n:\ |d_i-d|\ge0.1d\} &\le \sum_{i=1}^n \mathbb P\{|d_i-d|\ge0.1d\} \\ &\le n\cdot 2e^{-cd}. \end{aligned} $$如果 $d\ge C\log n$，且绝对常数 $C$ 足够大，那么这个概率至多为 $0.01$。这意味着以概率至少 $0.99$，补事件发生：对所有 $i\le n$，都有 $|d_i-d|<0.1d$。证明完成。
你可能会问 Proposition 2.5.1 中的条件 $d\gtrsim\log n$ 是否最优。它是最优的：如果 $d<(1-\varepsilon)\ln n$，就会出现孤立顶点，也就是 Exercise 1.10 中的“没有朋友的学生”，从而最小度为零。如果你还没有做 Exercises 1.9 和 1.10，现在可以试试，同时也可以做 Exercises 2.18-2.20。
2.6 次高斯分布
让我们重新审视独立随机变量 $X_i$ 的和的 Hoeffding 不等式：
$$ \mathbb P\left\{ \left|\sum_{i=1}^N a_iX_i\right| \ge t \right\} \le 2\exp\left(-\frac{ct^2}{\|a\|_2^2}\right) \quad\text{for all }t\ge0. \tag{2.14} $$
这个结果对 Rademacher 随机变量 $X_i$ 成立（Theorem 2.2.1）；更一般地，对任意均值为零的有界随机变量 $X_i$ 也成立（Theorem 2.2.6）；对标准正态随机变量 $X_i$ 也成立。为什么？ 查看学习笔记证明
这让我们想问：Hoeffding 不等式成立的最大分布类是什么？如果和 $\sum_{i=1}^N a_iX_i$ 只包含单项 $X_i$，那么 (2.14) 变为
$$ \mathbb P\{|X_i|>t\} \le 2e^{-ct^2} \quad\text{for all }t\ge0. \tag{2.15} $$
我们很快会证明，这个条件也是充分的。
满足 (2.15) 的分布称为次高斯分布。它们在高维概率及其应用中构成一个自然且常常是标准的分布类。
由于次高斯分布非常重要，找到 (2.15) 的其他等价表达会很有用。为了获得启发，先看标准正态随机变量 $X\sim N(0,1)$。它的矩母函数是
$$ \mathbb E\exp(\lambda X) = e^{\lambda^2/2} \quad\text{for all }\lambda\in\mathbb R, \tag{2.16} $$
并且在 Exercise 2.22 中，你将检查 $X$ 的绝对矩满足
$$ \|X\|_{L^p} = (\mathbb E|X|^p)^{1/p} \le C\sqrt p \quad\text{for all }p\ge1. \tag{2.17} $$ 查看学习笔记完整证明
事实证明，这些性质对于一般分布也是等价的：像 (2.15) 那样的次高斯尾部衰减、像 (2.16) 那样的矩母函数增长、以及像 (2.17) 那样的矩增长，都表达同一件事：给定分布被正态分布控制。
设 $X$ 是随机变量。下面性质等价，其中参数 $K_i>0$ 至多相差一个绝对常数因子。
(i) 尾部：存在 $K_1>0$，使得
$$ \mathbb P\{|X|\ge t\} \le 2\exp(-t^2/K_1^2) \quad\text{for all }t\ge0. $$(ii) 矩：存在 $K_2>0$，使得
$$ \|X\|_{L^p} = (\mathbb E|X|^p)^{1/p} \le K_2\sqrt p \quad\text{for all }p\ge1. $$(iii) $X^2$ 的 MGF：存在 $K_3>0$，使得
$$ \mathbb E\exp(X^2/K_3^2)\le2. $$此外，如果 $\mathbb EX=0$，那么性质 (i)-(iii) 还等价于下面性质：
(iv) MGF：存在 $K_4>0$，使得
$$ \mathbb E\exp(\lambda X) \le \exp(K_4^2\lambda^2) \quad\text{for all }\lambda\in\mathbb R. $$这个证明稍长，但很有启发性：你会看到如何把关于随机变量的一种信息转化为另一种信息。
(i) $\Rightarrow$ (ii) 假设性质 (i) 成立。把 $X$ 缩放为 $X/K_1$，可设 $K_1=1$。请检查这一步。对 $|X|^p$ 使用积分尾公式（Lemma 1.6.1），得到
$$ \begin{aligned} \mathbb E|X|^p &= \int_0^\infty \mathbb P\{|X|^p\ge u\}\,du \\ &= \int_0^\infty \mathbb P\{|X|\ge t\}\,p t^{p-1}\,dt \quad (u=t^p) \\ &\le \int_0^\infty 2e^{-t^2}p t^{p-1}\,dt \\ &= p\,\Gamma(p/2) \\ &\le 3p(p/2)^{p/2}. \end{aligned} $$最后一步使用了 $\Gamma(x)\le3x^x$ 对所有 $x\ge1/2$ 成立。请检查。取 $p$ 次方根即可得到性质 (ii)，例如 $K_2\le3$。
查看学习笔记证明(ii) $\Rightarrow$ (iii) 假设性质 (ii) 成立。把 $X$ 缩放为 $X/K_2$，可设 $K_2=1$。使用指数函数的 Taylor 级数展开，得到
$$ \mathbb E\exp(\lambda^2X^2) = \mathbb E\left[ 1+\sum_{p=1}^{\infty} \frac{(\lambda^2X^2)^p}{p!} \right] = 1+\sum_{p=1}^{\infty} \frac{\lambda^{2p}\mathbb E[X^{2p}]}{p!}. $$性质 (ii) 保证 $\mathbb E[X^{2p}]\le(2p)^p$，而 Lemma 1.7.8 给出 $p!\ge(p/e)^p$。代入这两个界，得到
$$ \mathbb E\exp(\lambda^2X^2) \le 1+\sum_{p=1}^{\infty} \frac{(2\lambda^2p)^p}{(p/e)^p} = \sum_{p=0}^{\infty}(2e\lambda^2)^p = \frac1{1-2e\lambda^2} = 2, $$其中选择 $\lambda=1/(2\sqrt e)$。这给出性质 (iii)，例如 $K_3=2\sqrt e$。
(iii) $\Rightarrow$ (i) 假设性质 (iii) 成立。和前面一样，可设 $K_3=1$。取指数并使用 Markov 不等式，得到
$$ \mathbb P\{|X|\ge t\} = \mathbb P\{e^{X^2}\ge e^{t^2}\} \le e^{-t^2}\mathbb E e^{X^2} \le 2e^{-t^2}. $$这证明了性质 (i)，例如 $K_1=1$。
为了证明“此外”部分，需要证明 (iii) $\Rightarrow$ (iv) 和 (iv) $\Rightarrow$ (i)。
(iii) $\Rightarrow$ (iv) 假设性质 (iii) 成立，并且可设 $K_3=1$。使用数值不等式
$$ e^x\le 1+x+\frac{x^2}{2}e^{|x|}, $$它来自带 Lagrange 余项的 Taylor 定理。令 $x=\lambda X$，并使用 $\mathbb EX=0$，得到
$$ \begin{aligned} \mathbb E e^{\lambda X} &\le 1+\frac{\lambda^2}{2}\mathbb E X^2 e^{|\lambda X|} \\ &\le 1+\frac{\lambda^2}{2}e^{\lambda^2/2}\mathbb E e^{X^2} \\ &\le (1+\lambda^2)e^{\lambda^2/2} \\ &\le e^{3\lambda^2/2}. \end{aligned} $$第二步使用了 $x^2\le e^{x^2/2}$ 与 $|\lambda x|\le\lambda^2/2+x^2/2$；第三步使用了性质 (iii) 中的 $\mathbb E e^{X^2}\le2$；最后一步使用了 $1+z\le e^z$。这证明了性质 (iv)，例如 $K_4=\sqrt{3/2}$。
(iv) $\Rightarrow$ (i) 假设性质 (iv) 成立，可设 $K_4=1$。应用我们在 Hoeffding 不等式（Theorem 2.2.1）证明中第一次学到的指数矩方法。令 $\lambda>0$ 为稍后选择的参数。取指数并使用 Markov 不等式，得到
$$ \mathbb P\{X\ge t\} = \mathbb P\{e^{\lambda X}\ge e^{\lambda t}\} \le e^{-\lambda t}\mathbb E e^{\lambda X} \le e^{-\lambda t}e^{\lambda^2} = e^{-\lambda t+\lambda^2}. $$对 $\lambda$ 优化，即取 $\lambda=t/2$，得到
$$ \mathbb P\{X\ge t\} \le e^{-t^2/4}. $$对 $-X$ 重复同样论证，得到 $\mathbb P\{X\le -t\}\le e^{-t^2/4}$。合并两个界，得到 $\mathbb P\{|X|\ge t\}\le2e^{-t^2/4}$。因此性质 (i) 成立，例如 $K_1=2$。命题得证。
你可能会问，为什么性质 (iv) 中假设了 $\mathbb EX=0$。在 Exercise 2.23 中，你将证明任何满足 (iv) 的随机变量都必须具有零均值。
查看学习笔记完整证明性质 (i) 和 (iii) 中的常数 $2$ 没有特殊含义；它可以替换为任何大于 $1$ 的绝对常数。请检查。
查看学习笔记证明2.6.1 次高斯范数
如果随机变量 $X$ 满足 Proposition 2.6.1 中等价性质 (i)-(iii) 中的任意一个，就称 $X$ 是次高斯的。它的次高斯范数记为 $\|X\|_{\psi_2}$，定义为满足性质 (iii) 的最小 $K_3$。换句话说，
$$ \|X\|_{\psi_2} = \operatorname*{inf}\left\{ K>0:\ \mathbb E\exp(X^2/K^2)\le 2 \right\}. \tag{2.18} $$在 Exercise 2.42 中，你会确认 $\|\cdot\|_{\psi_2}$ 确实在次高斯随机变量空间上定义了一个范数。 查看学习笔记完整证明 这个陈述的关键部分是三角不等式：任意随机变量 $X$ 和 $Y$，不要求独立，都满足
$$ \|X+Y\|_{\psi_2} \le \|X\|_{\psi_2} + \|Y\|_{\psi_2}. $$
下面这些随机变量都是次高斯的；你将在 Exercises 2.24 和 2.33 中计算它们的次高斯范数：
(a) normal；(b) Rademacher；(c) Bernoulli；(d) Binomial；(e) 任意有界随机变量。
反过来，exponential、Poisson、geometric、chi-squared、Gamma、Cauchy 和 Pareto 分布都不是次高斯的；见 Exercise 2.25。
查看次高斯例子证明 查看非次高斯例子证明根据次高斯范数的定义，Proposition 2.6.1 给出下面结论。
每个次高斯随机变量 $X$ 都满足下面这些界。
(i) 尾部：对所有 $t\ge0$，
$$ \mathbb P\{|X|\ge t\} \le 2\exp\left( -\frac{ct^2}{\|X\|_{\psi_2}^2} \right). $$(ii) 矩：对所有 $p\ge1$，
$$ \|X\|_{L^p} \le C\|X\|_{\psi_2}\sqrt p. $$(iii) $X^2$ 的 MGF：
$$ \mathbb E\exp\left( \frac{X^2}{\|X\|_{\psi_2}^2} \right) \le 2. $$(iv) MGF：如果 $\mathbb EX=0$，那么对所有 $\lambda\in\mathbb R$，
$$ \mathbb E\exp(\lambda X) \le \exp\left( C\lambda^2\|X\|_{\psi_2}^2 \right). $$这里 $C,c>0$ 是绝对常数。此外，在绝对常数因子意义下，$\|X\|_{\psi_2}$ 是使这些陈述分别成立的最小可能数。
还有许多其他等价方式可以描述次高斯分布；你可以在 Exercises 2.26-2.28 和 2.39 中发现其中一些。此外，如果不希望损失任何绝对常数因子，也可以用更精细的方式定义次高斯范数；现在可以尝试 Exercise 2.40。
2.7 次高斯 Hoeffding 与 Khintchine 不等式
上一节辛苦刻画了次高斯分布之后，现在看看这些结果有什么用。
方差的基本性质 (1.8) 推出：独立、均值为零的随机变量 $X_1,\ldots,X_N$ 满足 Pythagorean theorem：
$$ \left\|\sum_{i=1}^N X_i\right\|_{L^2}^2 = \sum_{i=1}^N \|X_i\|_{L^2}^2. \tag{2.19} $$
次高斯范数满足一个相似但稍弱的性质。
设 $X_1,\ldots,X_N$ 是独立、均值为零的次高斯随机变量。那么
$$ \left\|\sum_{i=1}^N X_i\right\|_{\psi_2}^2 \le C\sum_{i=1}^N \|X_i\|_{\psi_2}^2, $$其中 $C$ 是绝对常数。
查看学习笔记完整证明计算和 $S_N=\sum_{i=1}^N X_i$ 的矩母函数。对任意 $\lambda\in\mathbb R$，有
$$ \begin{aligned} \mathbb E\exp(\lambda S_N) &= \prod_{i=1}^N \mathbb E\exp(\lambda X_i) \quad\text{(by independence)}\\ &\le \prod_{i=1}^N \exp\left(C\lambda^2\|X_i\|_{\psi_2}^2\right) \quad\text{(by Proposition 2.6.6(iv))}\\ &= \exp(\lambda^2K^2), \end{aligned} $$其中
$$ K^2 = C\sum_{i=1}^N\|X_i\|_{\psi_2}^2. $$由 Proposition 2.6.1 中 (iii) $\Leftrightarrow$ (iv) 可知，这推出
$$ \mathbb E\exp(cS_N^2/K^2)\le2, $$其中 $c>0$ 是绝对常数。根据次高斯范数定义 (2.18)，得到 $\|S_N\|_{\psi_2}\le K/\sqrt c$，证明完成。
看到 Pythagorean identity (2.19)，你可能会问 Proposition 2.7.1 中的不等式能否反向。你将在 Exercises 2.33 和 2.34 中说明：如果 $X_i$ 同分布，答案是“可以”；但一般情形下答案是“不可以”。
2.7.1 次高斯 Hoeffding 不等式
使用 Proposition 2.6.6(i)，可以把 Proposition 2.7.1 改写成次高斯尾界。
设 $X_1,\ldots,X_N$ 是独立、均值为零的次高斯随机变量。那么，对每个 $t\ge0$，
$$ \mathbb P\left\{ \left|\sum_{i=1}^N X_i\right| \ge t \right\} \le 2\exp\left( -\frac{ct^2}{\sum_{i=1}^N\|X_i\|_{\psi_2}^2} \right). $$令 $X_i$ 服从 Rademacher 分布，并把 Theorem 2.7.3 应用于随机变量 $a_iX_i$。注意
$$ \|a_iX_i\|_{\psi_2} = |a_i|\cdot\|X_i\|_{\psi_2}, $$并且 $\|X_i\|_{\psi_2}$ 是绝对常数。为什么？于是得到
查看学习笔记证明 $$ \mathbb P\left\{ \left|\sum_{i=1}^N a_iX_i\right| \ge t \right\} \le 2\exp\left(-\frac{ct^2}{\|a\|_2^2}\right). \tag{2.20} $$这正是我们熟悉的 Rademacher 分布 Hoeffding 不等式（Theorem 2.2.1），只是指数中的绝对常数从 $1/2$ 变成了另一个 $c$。同样的推理也可用于恢复一般有界随机变量的 Hoeffding 不等式（Theorem 2.2.6），仍然只差绝对常数；见 Exercise 2.29。
2.7.2 次高斯 Khintchine 不等式
现在建立另一个经典结果：独立随机变量和的 $L^p$ 范数的双侧界。
设 $X_1,\ldots,X_N$ 是独立次高斯随机变量，均值为零、方差为一，并且 $a_1,\ldots,a_N\in\mathbb R$。那么对每个 $p\in[2,\infty)$，都有
$$ \left(\sum_{i=1}^N a_i^2\right)^{1/2} \le \left\|\sum_{i=1}^N a_iX_i\right\|_{L^p} \le CK\sqrt p \left(\sum_{i=1}^N a_i^2\right)^{1/2}, $$其中 $K=\operatorname*{max}_i\|X_i\|_{\psi_2}$，$C$ 是绝对常数。
查看学习笔记完整证明当 $p=2$ 时，我们实际上有等号。Pythagorean identity (2.19) 与单位方差假设给出
$$ \left\|\sum_{i=1}^N a_iX_i\right\|_{L^2} = \left( \sum_{i=1}^N a_i^2\|X_i\|_{L^2}^2 \right)^{1/2} = \left(\sum_{i=1}^N a_i^2\right)^{1/2}. $$因此，定理中的下界由 $L^p$ 范数单调性 (1.20) 得到。对上界，使用 Proposition 2.7.1：
$$ \begin{aligned} \left\|\sum_{i=1}^N a_iX_i\right\|_{\psi_2} &\le C\left( \sum_{i=1}^N a_i^2\|X_i\|_{\psi_2}^2 \right)^{1/2} \\ &\le CK\left(\sum_{i=1}^N a_i^2\right)^{1/2}. \end{aligned} $$最后应用 Proposition 2.6.6(ii)，得到 $L^p$ 上界。
你将在 Exercise 2.36 中把 Khintchine 不等式扩展到 $p\in[1,2]$。
2.7.3 次高斯变量的最大值
到目前为止，我们一直关注随机变量之和。那么其他可能非线性的函数呢？第 5 章会深入研究它们。这里先给出一个例子：Proposition 2.7.1 关于最大值的版本。
设 $X_1,\ldots,X_N$ 是次高斯随机变量，其中 $N\ge2$，不要求它们独立。那么
$$ \left\| \operatorname*{max}_{i\le N}X_i \right\|_{\psi_2} \le C\sqrt{\log N}\, \operatorname*{max}_{i\le N}\|X_i\|_{\psi_2}. \tag{2.21} $$特别地，
$$ \mathbb E\operatorname*{max}_{i\le N}X_i \le CK\sqrt{\log N}, \tag{2.22} $$其中 $K=\operatorname*{max}_{i\le N}\|X_i\|_{\psi_2}$。同样的界显然也适用于 $\operatorname*{max}_i |X_i|$。为什么？
查看学习笔记证明 查看学习笔记完整证明我们给出 (2.21) 的两种证明；选择你喜欢的一种即可。
第一种证明：并集界。 不失一般性，假设 $\max_i\|X_i\|_{\psi_2}=1$。为什么？对任意 $t\ge0$，有
$$ \mathbb P\left\{ \operatorname*{max}_{i\le N}X_i\ge t \right\} \le \sum_{i=1}^N\mathbb P\{X_i\ge t\} \le 2N\exp(-ct^2), $$其中次高斯尾界来自 Proposition 2.6.6(i)。如果 $N\le\exp(ct^2/2)$，那么上面的概率被 $2\exp(-ct^2/2)$ 控制，这比所需更强。如果 $N>\exp(ct^2/2)$，那么任意事件的概率都平凡地被 $2\exp(-ct^2/(3\ln N))$ 控制，因为这个量大于 $1$。因此，在任意情形下，
$$ \mathbb P\left\{ \operatorname*{max}_{i\le N}X_i\ge t \right\} \le 2\exp\left( -\frac{ct^2}{3\ln N} \right) \quad\text{for any }t\ge0. $$由 Proposition 2.6.6 中 (i) $\Leftrightarrow$ (iii) 可知，$\|\operatorname*{max}_{i\le N}X_i\|_{\psi_2}\le C\sqrt{\ln N}$，即得结论。
第二种证明：用和替换最大值。 仍假设 $\max_i\|X_i\|_{\psi_2}=1$，并记 $Z=\operatorname*{max}_{i\le N}|X_i|$。则
$$ \mathbb E e^{Z^2} = \mathbb E\operatorname*{max}_{i\le N}e^{X_i^2} \le \mathbb E\sum_{i=1}^N e^{X_i^2} = \sum_{i=1}^N\mathbb E e^{X_i^2} \le 2N. $$令 $M=\sqrt{2\ln(2N)}\ge1$。Jensen 不等式给出
$$ \mathbb E e^{Z^2/M^2} \le \left(\mathbb E e^{Z^2}\right)^{1/M^2} \le (2N)^{1/(2\ln(2N))} = \sqrt e <2. $$因此 $\|\operatorname*{max}_{i\le N}|X_i|\|_{\psi_2}\le M=\sqrt{2\ln(2N)}$，从而证明 (2.21)。
界 (2.22) 由 (2.21) 和 Proposition 2.6.6(ii) 在 $p=1$ 时推出。
Proposition 2.7.6 中出现的因子 $\sqrt{\log N}$ 是不可避免的：在 Exercise 2.38 中，你会看到独立同分布随机变量 $g_i\sim N(0,1)$ 满足
$$ \mathbb E\operatorname*{max}_{i\le N}|g_i| \approx \sqrt{2\ln N}. $$好消息是，对数因子增长很慢，常常可以忽略。这对采样很有利，因为它有助于防止极端离群点。平均而言，从正态分布抽取的 $N$ 个样本中，离均值最远的点也只在 $\sqrt{2\ln N}$ 个标准差之外。
2.7.4 中心化
概率论中的许多结果，例如次高斯 Hoeffding 不等式，都要求随机变量 $X_i$ 均值为零。当它们不满足时，可以通过减去均值对 $X_i$ 进行中心化。这样的中心化只会减小 $L^2$ 范数：
$$ \|X-\mathbb EX\|_{L^2} \le \|X\|_{L^2}. \tag{2.23} $$
这来自方差的一个极值性质（Exercise 0.2）。下面检查中心化也不会破坏次高斯范数。 查看学习笔记证明
任意次高斯随机变量 $X$ 都满足
$$ \|X-\mathbb EX\|_{\psi_2} \le C\|X\|_{\psi_2}. $$由于 $\|\cdot\|_{\psi_2}$ 是范数（Exercise 2.42），三角不等式给出
$$ \|X-\mathbb EX\|_{\psi_2} \le \|X\|_{\psi_2} + \|\mathbb EX\|_{\psi_2}. \tag{2.24} $$只需控制第二项。注意，对任意常数随机变量 $a$，显然有 $\|a\|_{\psi_2}\lesssim |a|$（Exercise 2.24(b)）。把它用于 $a=\mathbb EX$，并对函数 $f(x)=|x|$ 使用 Jensen 不等式，得到
$$ \|\mathbb EX\|_{\psi_2} \lesssim |\mathbb EX| \le \mathbb E|X| = \|X\|_{L^1} \lesssim \|X\|_{\psi_2}. $$最后一步使用了 Proposition 2.6.6(ii) 且 $p=1$。代回 (2.24) 即可完成证明。
2.8 次指数分布
次高斯分布类自然且相当宽泛。不过，它仍然漏掉了一些尾部比 Gaussian 更重的重要分布。例如，考虑一个标准正态随机向量 $g=(g_1,\ldots,g_N)\in\mathbb R^N$，其中坐标 $g_i$ 是独立的 $N(0,1)$ 随机变量。看它的 Euclidean 范数：
$$ \|g\|_2 = \left(\sum_{i=1}^N g_i^2\right)^{1/2}. $$
$\|g\|_2$ 是否集中在它的期望附近？一方面，$\|g\|_2$ 由独立随机变量 $g_i^2$ 的和构成，因此我们可能期待它有某种集中。另一方面，虽然 $g_i$ 是次高斯随机变量，但 $g_i^2$ 不是。事实上，回忆 Gaussian tail 的行为（Proposition 2.1.2），可以看出
$$ \mathbb P\{g_i^2>t\} = \mathbb P\{|g|>\sqrt t\} \sim \exp\left(-\frac{(\sqrt t)^2}{2}\right) = \exp(-t/2). $$
所以 $g_i^2$ 的尾部表现得像指数分布，严格重于次高斯尾。这使得在研究 $\|g\|_2$ 的集中时，不能直接使用目前建立的 Hoeffding 不等式（Theorem 2.7.3）等工具。
2.8.1 次指数性质
基于这个动机，我们来看具有指数型或更轻尾部衰减的分布，这类分布称为次指数分布。分析会和 Section 2.6 中对次高斯分布的分析很相似，所以这里推进得稍快一些。下面是 Proposition 2.6.1 的次指数版本。
设 $X$ 是随机变量。下面性质等价，其中参数 $K_i>0$ 至多相差一个绝对常数因子。
(i) 尾部：存在 $K_1>0$，使得
$$ \mathbb P\{|X|\ge t\} \le 2\exp(-t/K_1) \quad\text{for all }t\ge0. $$(ii) 矩：存在 $K_2>0$，使得
$$ \|X\|_{L^p} = (\mathbb E|X|^p)^{1/p} \le K_2p \quad\text{for all }p\ge1. $$(iii) $|X|$ 的 MGF：存在 $K_3>0$，使得
$$ \mathbb E\exp(|X|/K_3)\le2. $$此外，如果 $\mathbb EX=0$，那么性质 (i)-(iii) 还等价于下面性质：
(iv) MGF：存在 $K_4>0$，使得
$$ \mathbb E\exp(\lambda X) \le \exp(K_4^2\lambda^2) \quad\text{for all }\lambda\text{ such that }|\lambda|\le\frac1{K_4}. $$性质 (i)-(iii) 的等价性可以像 Proposition 2.6.1 那样证明；你将在 Exercise 2.41 中完成。性质 (iv) 与其他性质的等价稍有不同，所以这里证明它。
(iii) $\Rightarrow$ (iv) 假设性质 (iii) 成立。不失一般性，可设 $K_3=1$。为什么？使用数值不等式
$$ e^x\le 1+x+\frac{x^2}{2}e^{|x|}, $$它来自带 Lagrange 余项的 Taylor 定理。假设 $|\lambda|\le1/2$，并代入 $x=\lambda X$，得到
$$ \begin{aligned} \mathbb E e^{\lambda X} &\le 1+\frac{\lambda^2}{2}\mathbb E X^2 e^{|\lambda X|} \quad\text{(since }\mathbb EX=0\text{)}\\ &\le 1+2\lambda^2\mathbb E e^{|X|} \quad\text{(since }x^2\le4e^{|x|/2}\text{ and }e^{|\lambda x|}\le e^{|x|/2}\text{)}\\ &\le 1+4\lambda^2 \quad\text{(by assumption (iii))}\\ &\le e^{4\lambda^2}. \end{aligned} $$这给出性质 (iv)，例如 $K_4=2$。
(iv) $\Rightarrow$ (i) 不失一般性，假设性质 (iv) 在 $K_4=1$ 时成立。取指数、应用 Markov 不等式，并用 $\lambda=1$ 时的 (iv)，得到
$$ \mathbb P\{X\ge t\} = \mathbb P\{e^X\ge e^t\} \le e^{-t}\mathbb E e^X \le e^{1-t}. $$类似地，$\mathbb P\{-X\ge t\}\le e^{1-t}$。由并集界，
$$ \mathbb P\{|X|\ge t\} \le 2e^{1-t}. $$当 $t\ge3/2$ 时，它进一步被 $2e^{-t/3}$ 控制；当 $t<3/2$ 时，$2e^{-t/3}\ge1$，概率平凡地被这个量控制。因此性质 (i) 成立，例如 $K_1=3$。
你可能会惊讶地看到，次高斯分布和次指数分布在原点附近有同样的 MGF 界，也就是 Propositions 2.6.1 和 2.8.1 中的性质 (iv)。但这对任何均值为零的随机变量 $X$ 来说都是自然的。为了看出这一点，简单起见，假设 $X$ 有界且方差为一。用 Taylor 展开的前两项近似 MGF：
$$ \mathbb E\exp(\lambda X) \approx \mathbb E\left[ 1+\lambda X+\frac{\lambda^2X^2}{2} \right] = 1+\frac{\lambda^2}{2} \approx e^{\lambda^2/2} $$当 $\lambda\to0$ 时成立。对标准正态分布 $N(0,1)$，这个近似变为等式，见 (2.16)。对次高斯分布，Proposition 2.6.1(iv) 说这样的界对所有 $\lambda$ 成立，这刻画了次高斯分布。对次指数分布，Proposition 2.8.1(iv) 说这样的界只需对小的 $\lambda$ 成立，这刻画了次指数分布。
对次指数变量，MGF 界只能保证在零附近成立。事实上，若 $X\sim\operatorname{Exp}(1)$，那么它的 MGF 在 $\lambda\ge1$ 时为无穷大。请检查。
查看学习笔记证明2.8.2 次指数范数
如果随机变量 $X$ 满足 Proposition 2.8.1 中等价性质 (i)-(iii) 中的任意一个，就称 $X$ 是次指数的。它的次指数范数记为 $\|X\|_{\psi_1}$，定义为性质 (iii) 中最小的 $K_3$。换句话说，
$$ \|X\|_{\psi_1} = \operatorname*{inf}\left\{ K>0:\ \mathbb E\exp(|X|/K)\le2 \right\}. \tag{2.25} $$在 Exercise 2.42 中，你会确认 $\|\cdot\|_{\psi_1}$ 确实在次指数随机变量空间上定义了一个范数。
次高斯分布和次指数分布有密切联系。它们的定义直接推出下面结果。请检查。 查看学习笔记证明
$X$ 是次高斯随机变量，当且仅当 $X^2$ 是次指数随机变量，并且
$$ \|X^2\|_{\psi_1} = \|X\|_{\psi_2}^2. $$更一般地：
如果 $X$ 和 $Y$ 是次高斯随机变量，那么 $XY$ 是次指数随机变量，并且
$$ \|XY\|_{\psi_1} \le \|X\|_{\psi_2}\|Y\|_{\psi_2}. $$不失一般性，可设 $\|X\|_{\psi_2}=\|Y\|_{\psi_2}=1$。为什么？根据定义，这意味着 $\mathbb E\exp(X^2)\le2$ 且 $\mathbb E\exp(Y^2)\le2$。于是
$$ \begin{aligned} \mathbb E\exp(|XY|) &\le \mathbb E\exp\left(\frac{X^2}{2}+\frac{Y^2}{2}\right) \quad\text{(since }|ab|\le a^2/2+b^2/2\text{)}\\ &= \mathbb E\left[ \exp(X^2/2)\exp(Y^2/2) \right]\\ &\le \frac12\mathbb E\left[\exp(X^2)+\exp(Y^2)\right]\\ &\le \frac12(2+2) = 2. \end{aligned} $$第三步再次使用了 $ab\le a^2/2+b^2/2$。由定义可知 $\|XY\|_{\psi_1}\le1$，证明完成。
下面随机变量都是次指数的。请检查：
(a) 任意次高斯随机变量；(b) 任意次高斯随机变量的平方（Lemma 2.8.6）；(c) exponential；(d) Poisson；(e) geometric；(f) chi-squared；(g) Gamma。
反过来，Cauchy 和 Pareto 分布不是次指数的。请检查。
查看学习笔记证明次高斯分布的许多性质可以推广到次指数分布。一个例子是中心化（Lemma 2.7.8），它的次指数版本为
$$ \|X-\mathbb EX\|_{\psi_1} \le C\|X\|_{\psi_1}. \tag{2.26} $$
你将在 Exercise 2.44 中检查这个性质以及一些其他性质。 查看学习笔记完整证明
我们已经引入了随机变量的许多性质。它们如何相互联系？下面是一条蕴含链：
$$ X\text{ is bounded a.s.} \Rightarrow X\text{ is subgaussian} \Rightarrow X\text{ is subexponential} \Rightarrow X\text{ has moments of all orders} \Rightarrow X\text{ has finite variance} \Rightarrow X\text{ has finite mean}. $$定量地，对应下面的范数不等式链：
$$ \|X\|_{L^1} \le \|X\|_{L^2} \le \|X\|_{L^p} \lesssim \|X\|_{\psi_1} \lesssim \|X\|_{\psi_2} \lesssim \|X\|_{L^\infty}. $$这里对每个 $p\in[2,\infty)$ 都成立，其中 $\lesssim$ 符号在其中一个不等式中隐藏了一个 $O(p)$ 因子，在另外两个不等式中隐藏绝对常数因子。请解释每个不等式为什么成立。
查看学习笔记证明次高斯分布和次指数分布属于更宽泛的 $\psi_\alpha$ 分布族。Orlicz 空间和范数提供了更一般的框架。你将在 Exercises 2.43 和 2.42 中探索这些内容。
查看学习笔记：Orlicz 直觉链 查看概率论背景附录：校正版大偏差旁注2.9 Bernstein 不等式
我们现在可以陈述并证明一个适用于次指数分布的 Hoeffding 不等式版本。
设 $X_1,\ldots,X_N$ 是独立、均值为零的次指数随机变量。那么，对每个 $t\ge 0$，都有
$$ \mathbb{P}\Biggl\{ \Bigl|\sum_{i=1}^N X_i\Bigr|\ge t \Biggr\} \le 2\exp\Biggl[ -c\min\Biggl( \frac{t^2}{\sum_{i=1}^N \|X_i\|_{\psi_1}^2}, \frac{t}{\max_i \|X_i\|_{\psi_1}} \Biggr) \Biggr], $$其中 $c>0$ 是一个绝对常数。
查看学习笔记完整证明如果这个界看起来有些复杂，不必担心。证明之后我们会把它拆开，并给出一个更便于使用的形式。
我们使用在 Hoeffding 和 Chernoff 不等式证明中已经见过的指数矩方法。记
$$ S_N=\sum_{i=1}^N X_i. $$取参数 $\lambda>0$，把事件 $S_N\ge t$ 两边乘以 $\lambda$，再指数化，并使用 Markov 不等式和独立性，得到
$$ \mathbb{P}\{S_N\ge t\} \le e^{-\lambda t}\prod_{i=1}^N \mathbb{E}\exp(\lambda X_i). \tag{2.27} $$为了控制每个 $X_i$ 的矩母函数，我们使用 Proposition 2.8.1(iv)。它说明，只要 $\lambda$ 足够小，即
$$ |\lambda| \le \frac{c}{\max_i \|X_i\|_{\psi_1}}, \tag{2.28} $$就有
$$ \mathbb{E}\exp(\lambda X_i) \le \exp\bigl(C\lambda^2\|X_i\|_{\psi_1}^2\bigr). $$代回 (2.27)，可得
$$ \mathbb{P}\{S_N\ge t\} \le \exp\bigl(-\lambda t+C\lambda^2\sigma^2\bigr), \qquad \sigma^2=\sum_{i=1}^N\|X_i\|_{\psi_1}^2. $$现在在约束 (2.28) 下最小化右侧表达式。取
$$ \lambda = \min\Biggl( \frac{t}{2C\sigma^2}, \frac{c}{\max_i \|X_i\|_{\psi_1}} \Biggr), $$于是得到右尾界
$$ \mathbb{P}\{S_N\ge t\} \le \exp\Biggl[ -\min\Biggl( \frac{t^2}{4C\sigma^2}, \frac{ct}{2\max_i \|X_i\|_{\psi_1}} \Biggr) \Biggr]. $$对 $-X_i$ 重复同样论证，可以得到 $\mathbb{P}\{-S_N\ge t\}$ 的同样界。合并左右尾，证明完成。
为了让 Theorem 2.9.1 更方便使用，我们把它应用到 $a_iX_i$ 而不是 $X_i$ 上。这样就得到次指数分布版本的 (2.20)。
设 $X_1,\ldots,X_N$ 是独立、均值为零的次指数随机变量，并设 $a=(a_1,\ldots,a_N)\in\mathbb{R}^N$。那么，对每个 $t\ge 0$，都有
$$ \mathbb{P}\Biggl\{ \Bigl|\sum_{i=1}^N a_iX_i\Bigr|\ge t \Biggr\} \le 2\exp\Biggl[ -c\min\Biggl( \frac{t^2}{K^2\|a\|_2^2}, \frac{t}{K\|a\|_\infty} \Biggr) \Biggr], $$其中
$$ K=\max_i \|X_i\|_{\psi_1}. $$与 Hoeffding 不等式（Theorem 2.7.3）不同，Bernstein 不等式（Theorem 2.9.1）同时包含高斯尾和指数尾。高斯尾并不意外，因为这是中心极限定理所暗示的行为。指数尾也是必要的，因为单个次指数项 $X_i$ 的尾部就可能大到
$$ \exp\bigl(-ct/\|X_i\|_{\psi_1}\bigr), $$这严格重于高斯尾。令人惊讶的是，Theorem 2.9.1 中的指数尾并不会比单个项所能给出的尾界更差；真正控制它的是具有最大次指数范数的那个项。
像中心极限定理那样把和归一化，并把共同的次指数尺度吸收到常数中，可以从 Corollary 2.9.2 得到
$$ \mathbb{P}\Biggl\{ \Bigl|\frac{1}{\sqrt{N}}\sum_{i=1}^N X_i\Bigr|\ge t \Biggr\} \le \begin{cases} 2\exp(-ct^2), & t\le \sqrt{N},\\ 2\exp(-ct\sqrt{N}), & t\ge \sqrt{N}. \end{cases} $$在小偏差范围 $t\le\sqrt{N}$ 内，我们得到高斯型尾界。这个范围会随着 $N$ 增大而扩张，反映了中心极限定理力量的增强。另一方面，在大偏差范围 $t\ge\sqrt{N}$ 内，尾界仍然是更重的指数型，并由单个占优项 $X_i$ 驱动。图 2.3 展示了这一现象；我们在 Remark 2.3.5 中见过类似行为。
查看概率论背景附录：大偏差尺度说明
本章最后再提一个对各项方差敏感的 Bernstein 不等式版本。它的代价是需要更强的假设：每个 $X_i$ 都几乎处处有界。
设 $X_1,\ldots,X_N$ 是独立、均值为零的随机变量，并且对所有 $i$ 都满足 $|X_i|\le K$。那么，对每个 $t\ge 0$，都有
$$ \mathbb{P}\Biggl\{ \Bigl|\sum_{i=1}^N X_i\Bigr|\ge t \Biggr\} \le 2\exp\Biggl( -\frac{t^2/2}{\sigma^2+Kt/3} \Biggr), $$其中
$$ \sigma^2=\sum_{i=1}^N \mathbb{E}X_i^2 $$是这个和的方差。
你将在 Exercise 2.47 中证明这个 Bernstein 不等式版本。 查看学习笔记完整证明
2.10 注记
集中不等式覆盖了一个很广阔的领域，我们会在第 5 章中继续深入。Hoeffding、Chernoff 和 Bernstein 不等式的各种形式以及相关结果，可参见 [52]、[344, Chapter 2]、[17, Appendix A]、[249, Chapter 4]、[210]、[127, Chapter 7]、[21, Section 3.5.4]、[284, Chapter 1]、[24, Chapter 4]。
Proposition 2.1.2 中 Gaussian tails 上界的证明借自 [116, Theorem 1.4]。若想进一步了解 Exercise 2.3 中提到的 Mills ratio，可参见 [133]。
带有右侧额外因子 $3$ 的 Berry-Esseen 中心极限定理（Theorem 2.1.4）可见于例如 [116, Section 2.4.d]；书中说明目前已知的最佳因子约为 $0.47$ [302]。
本章用来推出集中不等式的指数矩方法，由 S. Bernstein [38, 39, 40] 开创。Chernoff 不等式（Theorem 2.3.1）的早期形式出现在 [83]。Hoeffding 不等式（Theorem 2.2.6）最早由 [161] 证明。
综述 [219] 探讨了 Section 2.4 中引入的均值估计问题的多种方法。median-of-means 估计量自 1980 年代以来就已被使用，它出现在 A. Nemirovsky 与 D. Yudin [256] 以及 M. Jerrum、L. Valiant 与 V. Vazirani [177] 的早期工作中。Theorem 2.4.1 中对 median-of-means 估计量的分析主要沿用 [219]。Exercise 2.17 中那类不可能性结果可见于 [99, 219]。
Section 2.5 只是触及了随机图丰富理论的一角。[47, 174, 131] 对随机图理论给出了系统介绍。本节以及 Exercises 2.18 和 2.19 中讨论的随机图顶点度数已有大量研究；许多渐近 sharp 的结果可参见 [131, Chapter 3]。Exercise 2.20 中研究的扩张性质与 expander mixing lemma 最为接近。若想进一步了解 expander graphs 的丰富理论，可参见综述 [164]。
Section 2.6 中讨论的次高斯分布由 J. P. Kahane [179] 引入。Sections 2.6-2.7 中讨论的一些基本性质最初建立于 [179, 68]。在这些早期工作中，次高斯分布要求均值为零，并且次高斯范数的定义对应 Exercise 2.40 中讨论的 exact subgaussian norm。关于 exact subgaussian norm（Exercise 2.40）的基本性质及其与 Orlicz 范数（Exercise 2.42）的关系，可参见现代论述 [285]。Sections 2.6-2.9 的表述主要遵循 [340]。
Rademacher 分布的 Khintchine 不等式原始版本（Theorem 2.7.5，Exercise 2.36）出现在 [183, 216]。Rademacher 分布的 sharp Khintchine 不等式版本及相关结果可见于 [311, 152, 192, 252, 160]，也可参见 [127, Theorem 8.5]；历史说明见 [21, Section 3.7]。
Bernstein 不等式的若干形式出现在 S. Bernstein 的原始工作 [38, 39, 40] 中；关于 S. Bernstein 贡献的历史说明，可参见 [21, Section 3.7]。Bernstein 不等式（Corollary 2.9.2）中对次指数范数的依赖常常可以改进 [176]。一般 $\psi_\alpha$ 分布的集中不等式可参见例如 [79, Theorem 1.2.8] 和 [210]。
Bennett 不等式（Exercise 2.48）很可能最早发表于 [35, 36]；另见 [161]。
Exercises
许多随机变量都会围绕均值集中；特别地，超过均值的概率通常是常数量级。下面给出一个集中性很差的例子，其中这个概率是指数小的。
设 $X_1,\ldots,X_n$ 是独立随机变量，且都服从 $[0,1]$ 上的均匀分布。证明它们的乘积
$$ Y_n:=X_1\cdots X_n $$满足
$$ (0.5)^n \le \mathbb{P}\{Y_n\ge \mathbb{E}Y_n\} \le (0.95)^n. $$ 查看学习笔记完整证明Proposition 2.1.2 中的下界留作了未证结论；现在来证明它。设 $g\sim N(0,1)$。证明：对所有 $t>0$，都有
$$ \mathbb{P}\{g\ge t\} \ge \frac{t}{t^2+1}\cdot \frac{1}{\sqrt{2\pi}}e^{-t^2/2}. $$为此，把左右两边的差看作 $t$ 的函数。检查这个函数会随着 $t$ 增大而递减到 $0$。
查看学习笔记完整证明虽然对 $g\sim N(0,1)$，Gaussian tail $\mathbb{P}\{g>t\}$ 不能对所有 $t$ 都解析地计算出来，但它可以展开成下面的级数：
$$ \frac{\mathbb{P}\{g>t\}}{f(t)} = \frac{1}{t} - \frac{1}{t^3} + \frac{1\cdot3}{t^5} - \frac{1\cdot3\cdot5}{t^7} +\cdots \quad\text{for }t>1, \tag{2.29} $$其中
$$ f(t)=\frac{1}{\sqrt{2\pi}}e^{-t^2/2} $$是 $g$ 的密度。而且，这个比值夹在该级数任意一对相邻部分和之间。例如，
$$ \frac{1}{t}-\frac{1}{t^3} \le \frac{\mathbb{P}\{g>t\}}{f(t)} \le \frac{1}{t}-\frac{1}{t^3}+\frac{3}{t^5} \quad\text{for }t>0. \tag{2.30} $$按以下步骤证明 (2.30)：
(a) 检查对所有 $x$ 都有
$$ f'(x)+xf(x)=0. $$(b) 使用 (a) 中的等式，对
$$ \mathbb{P}\{g>t\}=\int_t^\infty f(x)\,dx $$分部积分。重复这个过程。
查看学习笔记完整证明证明 $g\sim N(0,1)$ 满足：
(a) 对所有 $t>0$，
$$ \mathbb{E}\,g\mathbf{1}_{\{g>t\}} = \frac{1}{\sqrt{2\pi}}e^{-t^2/2}. $$(b) 对所有 $t>0$，
$$ \mathbb{E}\,g^2\mathbf{1}_{\{g>t\}} \le \biggl(t+\frac{1}{t}\biggr) \frac{1}{\sqrt{2\pi}}e^{-t^2/2}. $$ 查看学习笔记完整证明证明数值界 (2.7)：
$$ \cosh(x)\le \exp(x^2/2) \quad\text{for all }x\in\mathbb{R}. $$ 查看学习笔记完整证明使用指数矩方法证明：若 $g\sim N(0,1)$，则
$$ \mathbb{P}\{g\ge t\} \le e^{-t^2/2} \quad\text{for all }t\ge 0. $$虽然这个界比 (2.3) 的常数因子更大，但在很多场景中仍然足够使用。
查看学习笔记完整证明设 $X_1,\ldots,X_N$ 是非负、独立、具有连续分布的随机变量。假设所有 $X_i$ 的概率密度函数都被同一个常数 $K$ 一致控制。证明：对任意 $\varepsilon>0$，都有
$$ \mathbb{P}\Biggl\{ \sum_{i=1}^N X_i\le \varepsilon N \Biggr\} \le (eK\varepsilon)^N. $$ 查看学习笔记完整证明设 $X$ 和 $Y$ 是均值相同的随机变量。假设 $X$ 取值于区间 $[a,b]$，而 $Y$ 取值于两点集 $\{a,b\}$。证明：
$$ \mathbb{E}e^{\lambda X} \le \mathbb{E}e^{\lambda Y} \quad\text{for all }\lambda\in\mathbb{R}. $$ 查看学习笔记完整证明证明：任意取值于区间 $[a,b]$ 的随机变量 $X$ 都满足
$$ \mathbb{E}e^{\lambda(X-\mathbb{E}X)} \le \exp\biggl( \frac{\lambda^2(b-a)^2}{8} \biggr) \quad\text{for all }\lambda\in\mathbb{R}. $$按以下步骤证明：
(a) 说明不失一般性，可以假设 $X$ 的均值为零，$b-a=1$，并且 $X$ 只取两点集 $\{a,b\}$ 中的值。
(b) 计算累积母函数
$$ K(\lambda):=\log\mathbb{E}e^{\lambda X}, $$并检查 $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 的假设下，
$$ \mathbb{P}\{S_N\le t\} \le e^{-\mu}\biggl(\frac{e\mu}{t}\biggr)^t \quad\text{for every }0<t\le \mu. $$ 查看学习笔记完整证明证明：若二项随机变量 $S_N\sim\operatorname{Binom}(N,\mu/N)$，则它满足下面的 “reverse Chernoff” 不等式：
$$ \mathbb{P}\{S_N=t\} \ge e^{-\mu}\biggl(\frac{\mu}{t}\biggr)^t \quad\text{for every integer }t\in[\mu,N]. $$ 查看学习笔记完整证明由于 Poisson 极限定理（Theorem 1.7.6），我们有理由期待 Chernoff 不等式也适用于 Poisson 变量。确实如此。使用指数矩方法，证明对 $X\sim\operatorname{Pois}(\mu)$ 有以下尾界：
(a) Theorem 2.3.1 的版本：对每个 $t\ge\mu$，
$$ \mathbb{P}\{X\ge t\} \le e^{-\mu}(e\mu/t)^t. $$(b) Remark 2.3.2 的版本：对每个 $0<t\le\mu$，
$$ \mathbb{P}\{X\le t\} \le e^{-\mu}(e\mu/t)^t. $$(c) Corollary 2.3.4 的版本：对每个 $0\le\delta\le1$，
$$ \mathbb{P}\{|X-\mu|\ge \delta\mu\} \le 2\exp(-\delta^2\mu/3). $$(d) Exercise 2.12 的版本：对每个整数 $t>0$，
$$ \mathbb{P}\{X=t\} \ge e^{-\mu}(\mu/t)^t. $$ 查看学习笔记完整证明我们来扩展 Corollary 2.3.4。设 $X_i$ 是参数为 $p_i$ 的独立 Bernoulli 随机变量。考虑它们的和
$$ S_N=\sum_{i=1}^N X_i, $$并记其均值为 $\mu=\mathbb{E}S_N$。证明：
$$ \mathbb{P}\{|S_N-\mu|\ge \delta\mu\} \le 2\exp\biggl(-\frac{\delta^2\mu}{2+\delta}\biggr) \quad\text{for every }\delta\ge0. $$ 查看学习笔记完整证明说明 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$，都有$$ \mathbb{P}\Biggl\{ \bigl| \widehat{\mu}(X_1,\ldots,X_N)-\mu \bigr| \ge \frac{t\sigma}{\sqrt{N}} \Biggr\} \le 2e^{-ct^2}. $$
通过展开 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$，都有
$$ \mathbb{P}\{\mathbf{X}\in B\} \le e^{N\mu}\mathbb{P}\{\mathbf{Y}\in B\}. $$(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$ 满足
$$ d\le c(\log n)^{0.99}, $$则至少以 $0.99$ 的概率有
$$ c_1\frac{\log n}{\log\log n} \le \Delta(G) \le c_2\frac{\log n}{\log\log n}. $$ 查看学习笔记完整证明随机图 $G(n,p)$ 展现出一个显著性质：只要两个顶点子集 $S$ 和 $T$ 不是太小，连接它们的边数 $e(S,T)$ 就与这两个集合的大小成正比。这里 $e(S,T)$ 表示端点分别落在 $S$ 和 $T$ 中的边数。证明：存在绝对常数 $C>0$，使得至少以 $1-2^{-n}$ 的概率发生下述事件：
$$ 0.9p \le \frac{e(S,T)}{|S||T|} \le 1.1p $$对所有互不相交的顶点子集 $S,T$ 都成立，只要
$$ |S||T| \ge \frac{Cn}{p}. $$ 查看学习笔记完整证明设想我们有一个用于解决某个判定问题的算法，例如判断 $p$ 是否为素数。假设该算法会随机作出决定，并且给出正确结果的概率为 $\frac12+\varepsilon$，其中 $\varepsilon>0$；也就是说，它只比纯猜测稍好一点。为了提高性能，运行该算法 $N$ 次并取多数投票。证明：对任意 $\delta\in(0,1)$，只要
$$ N \ge \frac{1}{2\varepsilon^2} \ln\biggl(\frac{1}{\delta}\biggr), $$多数投票的答案至少以 $1-\delta$ 的概率正确。
查看学习笔记完整证明设 $g\sim N(0,1)$。
(a) 用 Gamma 函数表示 $g$ 的绝对矩：
$$ \mathbb{E}|g|^p = \frac{2^{p/2}}{\sqrt{\pi}} \Gamma\biggl(\frac{p+1}{2}\biggr) \quad\text{for each }p\ge1. $$(b) 推出 $g$ 的 $L^p$ 范数满足
$$ \|g\|_{L^p} = \bigl(\mathbb{E}|g|^p\bigr)^{1/p} = \sqrt{\frac{p}{e}}\,(1+o(1)) \quad\text{as }p\to\infty. $$ 查看学习笔记完整证明你可能会问，为什么 Proposition 2.6.1 的性质 (iv) 中要假设 $\mathbb{E}X=0$。证明：任何满足该性质的随机变量 $X$ 都必须有零均值。
查看学习笔记完整证明检查以下结论。
(a) Constant：若 $X=c$ a.s.，其中 $c$ 是常数，则
$$ \|X\|_{\psi_2}=\frac{|c|}{\sqrt{\ln 2}}. $$(b) Bounded：若 $X$ a.s. 有界，则
$$ \|X\|_{\psi_2} \le \frac{\|X\|_\infty}{\sqrt{\ln 2}}. $$(c) Rademacher：Rademacher 随机变量 $X$ 满足
$$ \|X\|_{\psi_2} = \frac{1}{\sqrt{\ln 2}}. $$(d) Normal：若 $X\sim N(0,\sigma^2)$，则
$$ \|X\|_{\psi_2} = \sigma\sqrt{\frac{8}{3}}. $$(e) Bernoulli：若 $X\sim\operatorname{Ber}(p)$，则
$$ \|X\|_{\psi_2} = \frac{1}{\sqrt{\ln(1+1/p)}}. $$ 查看学习笔记完整证明解释为什么 exponential、Poisson、geometric、chi-squared、Gamma、Cauchy 和 Pareto 分布都不是次高斯分布。
查看学习笔记完整证明在 Proposition 2.6.1 中，我们已经见过几种等价描述次高斯分布的方法。这里还有一种。证明：随机变量 $X$ 是次高斯的，当且仅当存在 $K>0$，使得
$$ \mathbb{E}\exp(\lambda^2X^2) \le \exp(\lambda^2K^2) \quad \text{for all }\lambda\text{ such that }|\lambda|\le\frac{1}{K}. \tag{2.31} $$更精确地，证明：若 $X$ 是次高斯，则 (2.31) 对 $K=\|X\|_{\psi_2}$ 成立。反过来，若 (2.31) 成立，则 $X$ 是次高斯，并且
$$ \|X\|_{\psi_2}\le 2K. $$ 查看学习笔记完整证明对两个随机变量 $X$ 和 $Y$，若
$$ \mathbb{P}\{X\ge t\} \le 2\mathbb{P}\{Y\ge t\} \quad\text{for all }t\in\mathbb{R}, \tag{2.32} $$则记 $X\preceq Y$。
(a) 证明：$X$ 是次高斯的，当且仅当存在 $K>0$，使得
$$ |X|\preceq K|g|, \qquad g\sim N(0,1). \tag{2.33} $$更精确地，证明：若 $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}$ 都有
$$ \mathbb{E}\Phi(X) \le \mathbb{E}\Phi(Y), $$则记 $X\precsim Y$。证明：$X$ 是次高斯的，当且仅当存在 $K>0$，使得
$$ |X|\precsim K|g|, \qquad g\sim N(0,1). \tag{2.34} $$更精确地，证明：若 $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}$。证明：
$$ \mathbb{P}\Biggl\{ \Bigl|\sum_{i=1}^N a_iX_i\Bigr| \ge \frac12 \biggl(\sum_{i=1}^N a_i^2\biggr)^{1/2} \Biggr\} \ge \frac{c}{K^4}, $$其中
$$ K=\max_{i\le N}\|X_i\|_{\psi_2}, $$且 $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}$ 无关。证明：
$$ \mathbb{E}X_i=0. $$ 查看学习笔记完整证明证明：任意两个独立、均值为零的次高斯随机变量 $X$ 和 $Y$ 都满足
$$ \|X+Y\|_{\psi_2} \asymp \|X\|_{\psi_2}+\|Y\|_{\psi_2}, $$其中 $\asymp$ 表示相差绝对常数因子。
查看学习笔记完整证明鉴于 Pythagorean identity (2.19)，一个自然问题是 Proposition 2.7.1 中的不等式能否反过来。在本题和下一题中，你将说明：若 $X_i$ 同分布，答案是“可以”；但一般情形下答案是“不可以”。
(a) 设 $X,X_1,X_2,\ldots,X_N$ 是 i.i.d.、均值为零的次高斯随机变量。证明：
$$ \biggl\|\sum_{i=1}^N X_i\biggr\|_{\psi_2} \asymp \sqrt{N}\,\|X\|_{\psi_2}, $$其中 $\asymp$ 表示相差绝对常数因子。
(b) 推出：若 $S_N\sim\operatorname{Binom}(N,p)$，则
$$ \|S_N-Np\|_{\psi_2} \asymp \sqrt{\frac{N}{\log(2/p)}}. $$ 查看学习笔记完整证明(a) 找到独立、均值为零的次高斯随机变量 $X_1,X_2,\ldots$，使得对任意 $N$ 和任意系数向量 $a=(a_1,\ldots,a_N)\in\mathbb{R}^N$，都有
$$ \biggl\|\sum_{i=1}^N a_iX_i\biggr\|_{\psi_2} \asymp \|a\|_\infty, $$其中 $\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$，则
$$ \|X\|_{\psi_2} \le \frac{Cb}{\sqrt{\log(2b/a)}}, $$其中 $C$ 是绝对常数。
(b) 给出一个例子说明：对任意 $a$ 和 $b$，(a) 中的界在绝对常数因子意义下都是紧的。
查看学习笔记完整证明在 Theorem 2.7.5 中，我们证明了 $p\in[2,\infty)$ 的 Khintchine 不等式。现在把它扩展到 $p\in[1,2]$。
(a) Extrapolation：证明任意具有有限 $L^3$ 范数的随机变量 $Z$ 都满足
$$ \|Z\|_{L^2} \le \|Z\|_{L^1}^{1/4}\|Z\|_{L^3}^{3/4}. $$(b) 设 $X_1,\ldots,X_N$ 是独立次高斯随机变量，均值为零、方差为一，并设 $a_1,\ldots,a_N\in\mathbb{R}$。证明：
$$ cK^{-3} \biggl(\sum_{i=1}^N a_i^2\biggr)^{1/2} \le \mathbb{E}\biggl|\sum_{i=1}^N a_iX_i\biggr| \le \biggl(\sum_{i=1}^N a_i^2\biggr)^{1/2}, $$其中 $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$ 是一列次高斯随机变量，不要求独立。那么
$$ \biggl\| \sup_k \frac{X_k}{\sqrt{\log(2k)}} \biggr\|_{\psi_2} \le C\sup_k\|X_k\|_{\psi_2}, $$其中 $C$ 是绝对常数。
查看学习笔记完整证明我们来证明标准正态随机变量的 maximal inequality (2.22) 的一个渐近 sharp 版本。
(a) 设 $g_1,\ldots,g_N$ 是 $N(0,1)$ 随机变量，其中 $N\ge2$，不要求它们独立。证明：
$$ \mathbb{E}\max_{i\le N} g_i \le \sqrt{2\ln N} \quad\text{and}\quad \mathbb{E}\max_{i\le N}|g_i| \le \sqrt{2\ln(2N)}. $$(b) 证明：若 $g_1,g_2,\ldots$ 是独立的 $N(0,1)$ 随机变量，则当 $N\to\infty$ 时，
$$ \mathbb{E}\max_{i\le N} g_i = \sqrt{2\ln N}\,(1+o(1)) \quad\text{and}\quad \mathbb{E}\max_{i\le N}|g_i| = \sqrt{2\ln N}\,(1+o(1)). $$ 查看学习笔记完整证明证明：随机变量 $X$ 是次高斯的，当且仅当存在 $K>0$，使得
$$ \mathbb{E}\max_{i\le N}|X_i| \le K\sqrt{\log N} \quad\text{for any }N=2,3,\ldots, \tag{2.35} $$其中 $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}$，都有
$$ \mathbb{E}e^{\lambda(X-\mu)} = e^{\sigma^2\lambda^2/2}. $$受此启发，定义随机变量 $X$ 的 subgaussian variance 为
$$ \operatorname{Var}_G(X) := \inf\Bigl\{ \sigma^2: \mathbb{E}e^{\lambda(X-\mathbb{E}X)} \le e^{\sigma^2\lambda^2/2} \text{ for all }\lambda\in\mathbb{R} \Bigr\}. $$回忆 $X$ 的 $L^2$ 范数可以写成
$$ \|X\|_{L^2}^2 = \mathbb{E}X^2 = \operatorname{Var}(X)+(\mathbb{E}X)^2. $$受此启发，通过下面的恒等式定义随机变量 $X$ 的 exact subgaussian norm：
$$ \|X\|_G^2 := \operatorname{Var}_G(X)+(\mathbb{E}X)^2. $$证明以下结论。
(a) exact subgaussian norm 确实在次高斯随机变量空间上定义了一个范数。
(b) exact subgaussian norm 与标准次高斯范数在绝对常数因子意义下等价：
$$ c_1\|X\|_{\psi_2} \le \|X\|_G \le c_2\|X\|_{\psi_2}. $$(c) 有
$$ \operatorname{Var}(X) \le \operatorname{Var}_G(X) \quad\text{and}\quad \|X\|_{L^2}\le\|X\|_G, $$并且当 $X$ 是正态分布时，上述不等式取等号。
(d) 若 $X_1,\ldots,X_N$ 独立且均值为零，则
$$ \operatorname{Var}_G\biggl(\sum_{i=1}^N X_i\biggr) \le \sum_{i=1}^N \operatorname{Var}_G(X_i). $$把它改写为
$$ \biggl\|\sum_{i=1}^N X_i\biggr\|_G^2 \le \sum_{i=1}^N \|X_i\|_G^2, $$就得到 Proposition 2.7.1 的精确版本。
(e) Centering 的精确版本（Lemma 2.7.8）：
$$ \|X-\mathbb{E}X\|_G \le \|X\|_G. $$ 查看学习笔记完整证明通过修改 Proposition 2.6.1 的证明，证明 Proposition 2.8.1 中性质 (i)-(iii) 的等价性。
查看学习笔记完整证明下面给出一个一般框架，它覆盖了我们目前见过的大多数范数。设 $\psi:[0,\infty)\to[0,\infty)$ 是非递减、凸函数，且 $\psi(0)=0$。随机变量 $X$ 的 Orlicz 范数定义为
$$ \|X\|_\psi = \inf\Biggl\{ K>0: \mathbb{E}\psi\biggl(\frac{|X|}{K}\biggr)\le1 \Biggr\}. $$(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$，都有
$$ \mathbb{P}\Biggl\{ \Bigl|\sum_{i=1}^N X_i\Bigr| \ge C\bigl(\sigma\sqrt{u}+Ku\bigr) \Biggr\} \le 2\exp(-u), $$其中
$$ \sigma^2=\sum_{i=1}^N \|X_i\|_{\psi_1}^2, \qquad K=\max_i\|X_i\|_{\psi_1}. $$ 查看学习笔记完整证明证明 Theorem 2.7.5 的下面这个次指数版本。设 $X_1,\ldots,X_N$ 是独立、均值为零的次指数随机变量，且 $a=(a_1,\ldots,a_N)\in\mathbb{R}^N$。那么，对每个 $p\in[2,\infty)$，都有
$$ \biggl\|\sum_{i=1}^N a_iX_i\biggr\|_{L^p} \le CK\bigl(\sqrt{p}\|a\|_2+p\|a\|_\infty\bigr), $$其中 $K=\max_i\|X_i\|_{\psi_1}$，且 $C$ 是绝对常数。
查看学习笔记完整证明(a) 设 $X$ 是均值为零的随机变量，且 $|X|\le K$ a.s.。证明 $X$ 的 MGF 满足下面的界：
$$ \mathbb{E}\exp(\lambda X) \le \exp\bigl(g(\lambda)\mathbb{E}X^2\bigr), \qquad g(\lambda) = \frac{\lambda^2/2}{1-|\lambda|K/3}, $$只要 $|\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$，都有
$$ \mathbb{P}\Biggl\{ \Bigl|\sum_{i=1}^N X_i\Bigr| \ge t \Biggr\} \le 2\exp\Biggl[ -\frac{\sigma^2}{K^2} h\biggl(\frac{Kt}{\sigma^2}\biggr) \Biggr], \tag{2.36} $$其中
$$ \sigma^2=\sum_{i=1}^N \mathbb{E}X_i^2, \qquad h(u)=(1+u)\ln(1+u)-u. $$按以下步骤证明：
(a) 设 $X$ 是均值为零且满足 $|X|\le K$ 的随机变量。证明对任意 $\lambda>0$，$X$ 的 MGF 满足
$$ \mathbb{E}\exp(\lambda X) \le \exp\Biggl[ \frac{\mathbb{E}X^2}{K^2} \bigl(e^{\lambda K}-1-\lambda K\bigr) \Biggr]. $$(b) 使用指数矩方法推出 (2.36)。
(c) 检查在小偏差范围中，也就是 $u=Kt/\sigma^2\approx0$ 时，有 $h(u)\approx u^2/2$。因此 Bennett 不等式给出近似 Gaussian 的尾界 $\exp(-t^2/\sigma^2)$，差一个绝对常数因子。
(d) 检查总有
$$ h(u)\ge \frac12 u\ln u. $$因此在大偏差范围中，Bennett 不等式给出 Poisson 型尾界
$$ 2\biggl(\frac{\sigma^2}{Kt}\biggr)^{t/(2K)}, $$类似于 Exercise 2.13。
查看学习笔记完整证明校对说明
concentration作为章节主题译为“集中现象”，作为具体工具译为“集中不等式”。subgaussian统一译为“次高斯”，subexponential统一译为“次指数”。moment generating function译为“矩母函数”，缩写 MGF 在笔记中保留。median-of-means estimator译为“均值的中位数估计量”，并在笔记中保留英文术语方便检索。