高维统计学讲义——第二章《2.1.2 次高斯随机变量和Hoeffding界（二）》

性质 2.5 Hoeffding届

这段内容介绍了次高斯性质的线性可加性，并给出了著名的 Hoeffding 不等式（Hoeffding bound）。

一、次高斯的线性运算封闭性

核心结论： 正如高斯性在独立随机变量相加时保持（独立高斯之和仍为高斯），次高斯性也保持。

具体来说，如果 $X_1$ 和 $X_2$ 独立，且分别具有次高斯参数 ${\sigma }_1$ 和 ${\sigma }_2$，那么：

$X_1+X_2$ 是次高斯的，参数为 $\sqrt{{\sigma }_1^2+{\sigma }_2^2}$

直观理解： 这个结论其实是在说“方差可以相加”。对于独立高斯变量，$X_1+X_2$ 的方差就是 ${\sigma }_1^2+{\sigma }_2^2$（注意：在次高斯定义里，参数 $\sigma$ 本质上扮演标准差的角色）。所以次高斯参数在独立求和时也是按平方和开根号的方式叠加，与高斯的行为完全一致。
这是 Exercise 2.13 的内容，我们来完整证明一下。

命题：设 $X_1$ 和 $X_2$ 相互独立，分别具有次高斯参数 ${\sigma }_1$ 和 ${\sigma }_2$（均值分别为 ${\mu }_1,{\mu }_2$）。则 $X_1+X_2$ 是次高斯的，参数为：

$\sigma =\sqrt{{\sigma }_1^2+{\sigma }_2^2}$

证明

要证明 $X_1+X_2$ 是次高斯的，需要证明对所有 $\lambda \in \mathbb{R}$：

$\mathbb{E}\left[e^{\lambda [(X_1+X_2)-({\mu }_1+{\mu }_2)]}\right]\le e^{\frac{({\sigma }_1^2+{\sigma }_2^2){\lambda }^2}{2}}$

第二步：利用独立性拆分期望

因为 $X_1$ 和 $X_2$ 独立，所以 $e^{\lambda (X_1-{\mu }_1)}$ 和 $e^{\lambda (X_2-{\mu }_2)}$ 也独立。独立随机变量乘积的期望等于期望的乘积：

$\mathbb{E}\left[e^{\lambda [(X_1+X_2)-({\mu }_1+{\mu }_2)]}\right]=\mathbb{E}\left[e^{\lambda (X_1-{\mu }_1)}\cdot e^{\lambda (X_2-{\mu }_2)}\right]$

$=\mathbb{E}\left[e^{\lambda (X_1-{\mu }_1)}\right]\cdot \mathbb{E}\left[e^{\lambda (X_2-{\mu }_2)}\right]$

第三步：代入各自的次高斯条件

由 $X_1$ 次高斯（参数 ${\sigma }_1$）：

$\mathbb{E}\left[e^{\lambda (X_1-{\mu }_1)}\right]\le e^{\frac{{\sigma }_1^2{\lambda }^2}{2}}$

由 $X_2$ 次高斯（参数 ${\sigma }_2$）：

$\mathbb{E}\left[e^{\lambda (X_2-{\mu }_2)}\right]\le e^{\frac{{\sigma }_2^2{\lambda }^2}{2}}$

第四步：相乘

$\mathbb{E}\left[e^{\lambda [(X_1+X_2)-({\mu }_1+{\mu }_2)]}\right]\le e^{\frac{{\sigma }_1^2{\lambda }^2}{2}}\cdot e^{\frac{{\sigma }_2^2{\lambda }^2}{2}}=e^{\frac{({\sigma }_1^2+{\sigma }_2^2){\lambda }^2}{2}}$

第五步：对照次高斯的定义

Definition 2.2 要求的是 $\mathbb{E}[e^{\lambda (X-\mu )}]\le e^{\frac{{\sigma }^2{\lambda }^2}{2}}$。对比上式：

$\frac{{\sigma }^2{\lambda }^2}{2}=\frac{({\sigma }_1^2+{\sigma }_2^2){\lambda }^2}{2}\Rightarrow {\sigma }^2={\sigma }_1^2+{\sigma }_2^2$

所以 $\sigma =\sqrt{{\sigma }_1^2+{\sigma }_2^2}$。

推广到 $n$ 个变量，完全相同的方法，只是期望拆成 $n$ 项相乘：

$\mathbb{E}\left[e^{\lambda {\sum }_{i=1}^n(X_i-{\mu }_i)}\right]={\prod }_{i=1}^n\mathbb{E}\left[e^{\lambda (X_i-{\mu }_i)}\right]\le {\prod }_{i=1}^n{e}^{\frac{{\sigma }_i^2{\lambda }^2}{2}}=e^{\frac{{\lambda }^2}{2}{\sum }_{i=1}^n{\sigma }_i^2}$

这就是 Proposition 2.5 中 ${\sum }_{i=1}^n{\sigma }_i^2$ 的由来，也是 Hoeffding 不等式分母里那个平方和的根源。

二、Proposition 2.5：Hoeffding 不等式

前提条件：

• $X_1,\dots ,X_n$ 相互独立
• 每个 $X_i$ 的均值为 ${\mu }_i=\mathbb{E}[X_i]$
• 每个 $X_i$ 是次高斯的，参数为 ${\sigma }_i$

结论： 对任意 $t\ge 0$，

$$\mathbb{P}\left[\sum _{i=1}^n(X_i-{\mu }_i)\ge t\right]\le \exp \left(-\frac{t^2}{2{\sum }_{i=1}^n{\sigma }_i^2}\right)\text{\hspace{1em}(2.10)}$$

三、推导思路（使用上面两个事实）

第一步：中心化和求和。
令 $Y={\sum }_{i=1}^n(X_i-{\mu }_i)={\sum }_{i=1}^n{X}_i-{\sum }_{i=1}^n{\mu }_i$。这是一个零均值随机变量。

第二步：使用次高斯的线性可加性。
由“独立次高斯之和仍是次高斯”的结论，$Y$ 是次高斯的，且其参数为：

${\sigma }_Y=\sqrt{{\sum }_{i=1}^n{\sigma }_i^2}$

第三步：代入基本次高斯尾界 (2.7)。
由 Definition 2.2 的推论（式 2.7），对一个均值 0、次高斯参数 ${\sigma }_Y$ 的随机变量 $Y$，有：

$\mathbb{P}[Y\ge t]\le e^{-\frac{t^2}{2{\sigma }_Y^2}}$

把 ${\sigma }_Y^2={\sum }_{i=1}^n{\sigma }_i^2$ 代入：

$\mathbb{P}[Y\ge t]\le \exp \left(-\frac{t^2}{2{\sum }_{i=1}^n{\sigma }_i^2}\right)$

这就是式 (2.10)。

四、Hoeffding 不等式的常见形式（有界情形）

特殊化： 如果每个 $X_i\in [a,b]$ 几乎必然，由 Exercise 2.4 我们知道 $X_i$ 的次高斯参数至多为：

${\sigma }_i=\frac{b-a}{2}$

代入 (2.10)：
分母 ${\sum }_{i=1}^n{\sigma }_i^2=n\cdot \frac{(b-a{)}^2}{4}$，于是：

$$\mathbb{P}\left[\sum _{i=1}^n(X_i-{\mu }_i)\ge t\right]\le \exp \left(-\frac{t^2}{2\cdot n\cdot \frac{(b-a{)}^2}{4}}\right)=e^{-\frac{2t^2}{n(b-a{)}^2}}\text{\hspace{1em}(2.11)}$$

这就是式 (2.11)，教科书中最常见的 Hoeffding 不等式形式。

核心直觉： Hoeffding 不等式告诉我们，独立有界随机变量之和的偏差概率，随 $t^2$ 以指数速度衰减，衰减速率与样本量 $n$ 和区间长度 $(b-a{)}^2$ 成反比。$n$ 越大、区间越窄，集中效果越强。它不需要知道每个变量的具体分布，只需知道它们的取值范围，非常通用。

定理2.6 次高斯的等价形式

这段内容是次高斯变量理论的核心总结。Theorem 2.6 告诉我们：对于零均值随机变量，"是次高斯"这件事可以从四个完全不同的角度来刻画，而且它们是等价的。这四个角度分别对应 MGF、尾部概率、矩的增长速度、以及对 MGF 的参数化处理。（$X$ 是零均值随机变量，即 $\mathbb{E}[X]=0$。）

(I) MGF 增长被高斯型控制

存在常数 $\sigma \ge 0$，使得对所有 $\lambda \in \mathbb{R}$：

$$\mathbb{E}[e^{\lambda X}]\le e^{\frac{{\lambda }^2{\sigma }^2}{2}}\text{\hspace{1em}(2.12a)}$$

含义： 这正是 Definition 2.2 的定义（因为零均值，所以 $X-\mu =X$）。这是次高斯性的原始定义，也是最直接的判据。

直观： MGF 被一个"高斯型"的指数函数控制，说明尾部衰减不慢于高斯。

(II) 尾部概率被高斯随机变量控制

存在常数 $c\ge 0$ 和高斯随机变量 $Z\sim \mathcal{N}(0,{\tau }^2)$，使得对所有 $s\ge 0$：

$$\mathbb{P}[|X|\ge s]\le c\mathbb{P}[|Z|\ge s]\text{\hspace{1em}(2.12b)}$$

含义： $X$ 的尾部概率（在常数倍意义下）被某个高斯变量的尾部概率控制。

直观： 这是最直观的"次高斯性"——尾比高斯轻或至少不比高斯重（差一个常数）。这也解释了为什么叫"次（sub）高斯"：它是"高斯之下"的。

为什么 (I) 能推出 (II)： 由 (I) 对 $X$ 和 $-X$ 分别应用 Chernoff 界，得到 $\mathbb{P}[|X|\ge s]\le 2e^{-\frac{s^2}{2{\sigma }^2}}$，而高斯尾部满足 $\mathbb{P}[|Z|\ge s]\ge C{e}^{-\frac{s^2}{2{\tau }^2}}$（对充分大的 $\tau$），所以两者可互相控制。

(III) 矩的增长被高斯型控制

存在常数 $\theta \ge 0$，使得对所有 $k=1,2,\dots$：

$$\mathbb{E}[X^{2k}]\le \frac{(2k)!}{2^{k}k!}{\theta }^{2k}\text{\hspace{1em}(2.12c)}$$

含义： 偶数阶矩（奇阶矩因为零均值+对称控制而类似处理）的增长速度被一个特定系数的 ${\theta }^{2k}$ 控制。

关键观察： $\frac{(2k)!}{2^{k}k!}=(2k-1)!!=1\cdot 3\cdot 5\cdots (2k-1)$，而标准高斯 $\mathcal{N}(0,{\theta }^2)$ 的 $2k$ 阶矩恰好是：

$\mathbb{E}[Z^{2k}]=(2k-1)!!\cdot {\theta }^{2k}=\frac{(2k)!}{2^{k}k!}{\theta }^{2k}$

所以 (III) 说的是：$X$ 的偶数阶矩不超过对应高斯变量的偶数阶矩。

直观： 矩的增长是次高斯的另一个等价刻画。第 $k$ 阶矩越大，尾部越重。这个条件意味着尾不比高斯重。

(IV) MGF 的一种"最优"参数化形式

存在常数 $\sigma \ge 0$，使得对所有 $\lambda \in [0,1)$：

$$\mathbb{E}\left[e^{\frac{\lambda X^2}{2{\sigma }^2}}\right]\le \frac{1}{\sqrt{1-\lambda }}\text{\hspace{1em}(2.12d)}$$

含义： 这是对 $e^{c{X}^2}$ 型函数的期望的控制，而不是对 $e^{\lambda X}$ 的控制。

直观： 这个条件等价于 $X^2$ 具有某种"亚指数（sub-exponential）"型的 MGF 控制。$\frac{1}{\sqrt{1-\lambda }}$ 是自由度为 1 的卡方分布（即标准高斯平方）的 MGF。所以 (IV) 说的是：$X^2$ 的 MGF 不超过标准高斯平方的 MGF。

为什么它等价于次高斯： 由 (I)，对 $X$ 应用切比雪夫型技巧，可以推出 (IV)；反过来，由 (IV) 通过泰勒展开也能推出 (III) 和 (I)。这个形式在很多高维概率的证明中（例如 Bernstein 型不等式）非常有用。

四条等价的逻辑关系

它们的等价性可以这样理解：

(I) $\iff$ (III)： MGF 的泰勒展开系数就是各阶矩。$e^{{\lambda }^2{\sigma }^2/2}={\sum }_k\frac{({\sigma }^2/2{)}^k{\lambda }^{2k}}{k!}$，而 $\mathbb{E}[e^{\lambda X}]={\sum }_k\frac{{\lambda }^{2k}\mathbb{E}[X^{2k}]}{(2k)!}$。逐项比较就得到 $\mathbb{E}[X^{2k}]\le \frac{(2k)!}{2^{k}k!}{\sigma }^{2k}$。

(I) $\iff$ (II)： 通过 Chernoff 界（(I) $\Rightarrow$ (II)）和高斯尾部下界（(II) $\Rightarrow$ (I) 的方向需要用积分估计）。

(I) $\iff$ (IV)： 两者都是对 MGF 的控制，只是参数化方式不同。可以通过变量替换和积分变换互相转换。

Theorem 2.6 给次高斯性提供了四个可互换使用的工具箱：

这四个刻画说明：次高斯性不是某个孤立的定义，而是一个在多处自然出现的"稳健"性质——无论你从 MGF、尾部、矩还是二次型 MGF 出发，都会到达同一个概念。这也是为什么次高斯成为高维概率和统计学习理论中最核心的假设之一。