第1章：预备定理

编辑：赵志民, 李一飞

---

本章将对书中出现或用到的重要定理进行回顾，并简要解释其证明和应用场景。对于可能不熟悉相关基础知识的读者，建议参考附录中的基础知识部分。通过这些定理的阐述，希望帮助读者更好地理解数学推导的核心原理，并为后续章节的学习打下坚实基础。大数定律（Law of Large Numbers）和集中不等式（Concentration Inequality）密切相关，二者共同揭示了随机变量偏离其期望值的行为。大数定律说明，当样本量足够大时，样本均值会以概率收敛于总体的期望值，反映了长期平均结果的稳定性。而集中不等式（定理 1.8 至 1.18）则更进一步，为随机变量在有限样本量下偏离其期望值的可能性提供了精确的上界。这些不等式描述了随机变量偏离期望值的程度有多大，通过对概率的约束，确保这种偏离发生的概率较小，从而为各种随机现象提供了更细致的控制。集中不等式在大数定律的基础上提供了有力的工具，用于分析有限样本中的波动。

1.1 Jensen 不等式

对于任意凸函数 $f$，则有：

$$f(\mathbb{E}[X])\le \mathbb{E}[f(X)]$$

成立。

证明

设 $p(x)$ 为 $X$ 的概率密度函数。由 Taylor 展开式及 $f$ 的凸性，可知 $\mathrm{\exists }\xi$ 使得：

$$\begin{array}{rl}f(x)& =f(\mathbb{E}[X])+f^{\prime }(\mathbb{E}[X])(x-\mathbb{E}[X])+\frac{f^{\prime \prime }(\xi )}{2}(x-\mathbb{E}[X]{)}^2\\ & \ge f(\mathbb{E}[X])+f^{\prime }(\mathbb{E}[X])(x-\mathbb{E}[X])\end{array}$$

对上式取期望，得到：

$$\begin{array}{rl}\mathbb{E}[f(X)]& =\int p(x)f(x)dx\\ & \ge f(\mathbb{E}[X])\int p(x)dx+f^{\prime }(\mathbb{E}[X])\int p(x)(x-\mathbb{E}[X])dx\\ & =f(\mathbb{E}[X])\end{array}$$

因此，原不等式得证。

如果 $f$ 是凹函数，则 Jensen 不等式变为：

$$f(\mathbb{E}[X])\ge \mathbb{E}[f(X)]$$

这一结论可以通过将上述证明中的 $f$ 替换为 $-f$ 得到。$◻$

1.2 Hölder 不等式

对于任意 $p,q\in {\mathbb{R}}^{+}$，且满足 $\frac{1}{p}+\frac{1}{q}=1$，则有：

$$\mathbb{E}[|XY|]\le (\mathbb{E}[|X{|}^p]{)}^{\frac{1}{p}}(\mathbb{E}[|Y{|}^q]{)}^{\frac{1}{q}}$$

成立。

证明

设 $f(x)$ 和 $g(y)$ 分别为 $X$ 和 $Y$ 的概率密度函数，定义：

$$M=\frac{|x|}{({\int }_X|x{|}^{p}f(x)dx{)}^{\frac{1}{p}}},N=\frac{|y|}{({\int }_Y|y{|}^{q}g(y)dy{)}^{\frac{1}{q}}}$$

代入 Young 不等式：

$$MN\le \frac{1}{p}{M}^p+\frac{1}{q}{N}^q$$

对该不等式两边同时取期望：

$$\begin{array}{rl}\frac{\mathbb{E}[|XY|]}{(\mathbb{E}[|X{|}^p]{)}^{\frac{1}{p}}(\mathbb{E}[|Y{|}^q]{)}^{\frac{1}{q}}}& =\frac{{\int }_{XY}|xy|f(x)g(y)dxdy}{({\int }_X|x{|}^{p}f(x)dx{)}^{\frac{1}{p}}({\int }_Y|y{|}^{q}g(y)dy{)}^{\frac{1}{q}}}\\ & \le \frac{{\int }_X|x{|}^{p}f(x)dx}{p{\int }_X|x{|}^{p}f(x)dx}+\frac{{\int }_Y|y{|}^{q}g(y)dy}{q{\int }_Y|y{|}^{q}g(y)dy}\\ & =\frac{1}{p}+\frac{1}{q}\\ & =1\end{array}$$

因此，Hölder 不等式得证。$◻$

1.3 Cauchy-Schwarz 不等式

当 $p=q=2$ 时，Hölder 不等式退化为 Cauchy-Schwarz 不等式：

$$\mathbb{E}[|XY|]\le \sqrt{\mathbb{E}[X^2]\cdot \mathbb{E}[Y^2]}$$

1.4 Lyapunov 不等式

对于任意 $0<r\le s$，有：

$$\sqrt[r]{\mathbb{E}[|X{|}^r]}\le \sqrt[s]{\mathbb{E}[|X{|}^s]}$$

证明

由 Hölder 不等式： 对任意 $p\ge 1$，有：

$$\begin{array}{rl}\mathbb{E}[|X{|}^r]& =\mathbb{E}[|X\cdot 1{|}^r]\\ & \le (\mathbb{E}[|X{|}^{rp}]{)}^{\frac{1}{p}}\cdot (\mathbb{E}[1^q]{)}^{\frac{1}{q}}\\ & =(\mathbb{E}[|X{|}^{rp}]{)}^{\frac{1}{p}}\end{array}$$

记 $s=rp\ge r$，则：

$$\mathbb{E}[|X{|}^r]\le (\mathbb{E}[|X{|}^s]{)}^{\frac{r}{s}}$$

因此，原不等式得证。$◻$

1.5 Minkowski 不等式

对于任意 $p\ge 1$，有：

$$\sqrt[p]{\mathbb{E}[|X+Y{|}^p]}\le \sqrt[p]{\mathbb{E}[|X{|}^p]}+\sqrt[p]{\mathbb{E}[|Y{|}^p]}$$

证明

由三角不等式和 Hölder 不等式，可得：

$$\begin{array}{rl}\mathbb{E}[|X+Y{|}^p]& \le \mathbb{E}[(|X|+|Y|)|X+Y{|}^{p-1}]\\ & =\mathbb{E}[|X\parallel X+Y{|}^{p-1}]+\mathbb{E}[|Y\parallel X+Y{|}^{p-1}]\\ & \le (\mathbb{E}[|X{|}^p]{)}^{\frac{1}{p}}(\mathbb{E}[|X+Y{|}^{(p-1)q}]{)}^{\frac{1}{q}}+(\mathbb{E}[|Y{|}^p]{)}^{\frac{1}{p}}(\mathbb{E}[|X+Y{|}^{(p-1)q}]{)}^{\frac{1}{q}}\\ & =[(\mathbb{E}[|X{|}^p]{)}^{\frac{1}{p}}+(\mathbb{E}[|Y{|}^p]{)}^{\frac{1}{p}}]\cdot \frac{\mathbb{E}[|X+Y{|}^p]}{(\mathbb{E}[|X+Y{|}^p]{)}^{\frac{1}{p}}}\end{array}$$

化简后即得证。$◻$

1.6 Bhatia-Davis 不等式

对 $X\in [a,b]$，有：

$$\mathbb{V}[X]\le (b-\mathbb{E}[X])(\mathbb{E}[X]-a)\le \frac{(b-a{)}^2}{4}$$

证明

因为 $a\le X\le b$，所以有：

$$\begin{array}{rl}0& \le \mathbb{E}[(b-X)(X-a)]\\ & =-\mathbb{E}[X^2]-ab+(a+b)\mathbb{E}[X]\end{array}$$

因此，

$$\begin{array}{rl}\mathbb{V}[X]& =\mathbb{E}[X^2]-\mathbb{E}[X{]}^2\\ & \le -ab+(a+b)\mathbb{E}[X]-\mathbb{E}[X^2]\\ & =(b-\mathbb{E}[X])(\mathbb{E}[X]-a)\end{array}$$

考虑 AM-GM 不等式：

$$xy\le (\frac{x+y}{2}{)}^2$$

将 $x=b-\mathbb{E}[X]$ 和 $y=\mathbb{E}[X]-a$ 带入并化简即得证。$◻$

1.7 Union Bound（Boole's）不等式

对于任意事件 $X$ 和 $Y$，有：

$$P(X\cup Y)\le P(X)+P(Y)$$

证明

根据概率的加法公式：

$$P(X\cup Y)=P(X)+P(Y)-P(X\cap Y)\le P(X)+P(Y)$$

由于 $P(X\cap Y)\ge 0$，因此不等式得证。$◻$

1.8 Markov 不等式

若 $X\ge 0$，则对于任意 $\epsilon >0$，有：

$$P(X\ge \epsilon )\le \frac{\mathbb{E}[X]}{\epsilon }$$

证明

由定义可得：

$$\mathbb{E}[X]={\int }_0^{\mathrm{\infty }}xp(x)dx\ge {\int }_{\epsilon }^{\mathrm{\infty }}xp(x)dx\ge \epsilon {\int }_{\epsilon }^{\mathrm{\infty }}p(x)dx=\epsilon P(X\ge \epsilon )$$

因此，原不等式得证。$◻$

1.9 Chebyshev 不等式

对于任意 $\epsilon >0$，有：

$$P(|X-\mathbb{E}[X]|\ge \epsilon )\le \frac{\mathbb{V}[X]}{{\epsilon }^2}$$

证明

利用 Markov 不等式，得到：

$$P(|X-\mathbb{E}[X]|\ge \epsilon )=P((X-\mathbb{E}[X]{)}^2\ge {\epsilon }^2)\le \frac{\mathbb{E}[(X-\mathbb{E}[X]{)}^2]}{{\epsilon }^2}=\frac{\mathbb{V}[X]}{{\epsilon }^2}$$

因此，Chebyshev 不等式得证。$◻$

1.10 Cantelli 不等式

对于任意 $\epsilon >0$，有：

$$P(X-\mathbb{E}[X]\ge \epsilon )\le \frac{\mathbb{V}[X]}{\mathbb{V}[X]+{\epsilon }^2}$$

证明

设 $Y=X-\mathbb{E}[X]$，则对于任意 $\lambda \ge 0$，有：

$$\begin{array}{rl}P(X-\mathbb{E}[X]\ge \epsilon )& =P(Y\ge \epsilon )\\ & =P(Y+\lambda \ge \epsilon +\lambda )\\ & =P((Y+\lambda {)}^2\ge (\epsilon +\lambda {)}^2)\\ & \le \frac{\mathbb{E}[(Y+\lambda {)}^2]}{(\epsilon +\lambda {)}^2}=\frac{\mathbb{V}[X]+{\lambda }^2}{(\epsilon +\lambda {)}^2}\end{array}$$

通过对 $\lambda$ 求导，得右端在 $\lambda =\frac{\mathbb{V}[X]}{\epsilon }$ 时取得最小值 $\frac{\mathbb{V}[X]}{\mathbb{V}[X]+{\epsilon }^2}$，因此：

$$P(X-\mathbb{E}[X]\ge \epsilon )\le \frac{\mathbb{V}[X]}{\mathbb{V}[X]+{\epsilon }^2}$$

原不等式得证。$◻$

值得注意的是，Cantelli 不等式是 Chebyshev 不等式的加强版，也称为单边 Chebyshev 不等式。通过类似的构造方法，可以推导出比 Cantelli 不等式更严格的上界。

1.11 Chernoff 界（Chernoff-Cramér 界）

对于任意 $\lambda >0,\epsilon >0$，有：

$$P(X\ge \epsilon )\le \underset{\lambda >0}{min}\frac{\mathbb{E}[e^{\lambda X}]}{e^{\lambda \epsilon }}$$

对于任意 $\lambda <0,\epsilon >0$，有：

$$P(X\le \epsilon )\le \underset{\lambda <0}{min}\frac{\mathbb{E}[e^{\lambda X}]}{e^{\lambda \epsilon }}$$

证明

应用 Markov 不等式，有：

$$P(X\ge \epsilon )=P(e^{\lambda X}\ge e^{\lambda \epsilon })\le \frac{\mathbb{E}[e^{\lambda X}]}{e^{\lambda \epsilon }},\lambda >0,\epsilon >0$$

同理，

$$P(X\le \epsilon )=P(e^{\lambda X}\le e^{\lambda \epsilon })\le \frac{\mathbb{E}[e^{\lambda X}]}{e^{\lambda \epsilon }},\lambda <0,\epsilon >0$$

因此，Chernoff 界得证。$◻$

基于上述 Chernoff 界的技术，我们可以进一步定义次高斯性：

定义 1 (随机变量的次高斯性)：若一个期望为零的随机变量 $X$ 的矩母函数满足 $\mathrm{\forall }\lambda \in {\mathbb{R}}^{+}$：

$$\mathbb{E}[e^{\lambda X}]\le \exp (\frac{{\sigma }^2{\lambda }^2}{2})$$

则称 $X$ 服从参数为 $\sigma$ 的次高斯分布。

实际上，Hoeffding 引理中的随机变量 $X$ 服从 $\frac{(b-a)}{2}$ 的次高斯分布。Hoeffding 引理也是次高斯分布的直接体现。次高斯性还有一系列等价定义，这里不作详细讨论。

次高斯分布有一个直接的性质：假设两个独立的随机变量 $X_1,X_2$ 都是次高斯分布的，分别服从参数 ${\sigma }_1,{\sigma }_2$，那么 $X_1+X_2$ 就是服从参数为 $\sqrt{{\sigma }_1^2+{\sigma }_2^2}$ 的次高斯分布。这个结果的证明可以直接利用定义来完成。

显然，并非所有常见的随机变量都是次高斯的，例如指数分布。为此可以扩大定义：

定义 2 (随机变量的次指数性)：若非负的随机变量 $X$ 的矩母函数满足 $\mathrm{\forall }\lambda \in (0,a)$：

$$\mathbb{E}[e^{\lambda X}]\le \frac{a}{a-\lambda }$$

则称 $X$ 服从参数为 $(\mathbb{V}[X],1/a)$ 的次指数分布。

同样地，次指数性也有一系列等价定义。一种不直观但更常用的定义如下：存在 $({\sigma }^2,b)$，使得 $\mathrm{\forall }|s|<1/b$：

$$\mathbb{E}[e^{s(X-\mathbb{E}[X])}]\le \exp (\frac{s^2{\sigma }^2}{2})$$

常见的次指数分布包括：指数分布，Gamma 分布，以及任何有界随机变量。

类似地，次指数分布对于加法也是封闭的：如果 $X_1,X_2$ 分别是服从 $({\sigma }_1^2,b_1)$ 和 $({\sigma }_2^2,b_2)$ 的次指数分布，那么 $X_1+X_2$ 是服从 $({\sigma }_1^2+{\sigma }_2^2,max(b_1,b_2))$ 的次指数分布。在高维统计问题中，次高斯分布和次指数分布的尾端控制能得到一些重要的结论。

1.12 Chernoff 不等式（乘积形式）

对于 $m$ 个独立同分布的随机变量 $x_i\in [0,1],i\in [m]$，设 $X=\sum _{i=1}^m{X}_i$，$\mu >0$ 且 $r\le 1$。若对所有 $i\le m$ 都有 $\mathbb{E}[x_i]\le \mu$，则：

$$\begin{array}{r}P(X\ge (1+r)\mu m)\le e^{-\frac{r^2\mu m}{3}},r\ge 0\\ P(X\le (1-r)\mu m)\le e^{-\frac{r^2\mu m}{2}},r\ge 0\end{array}$$

证明

应用 Markov 不等式，有：

$$P(X\ge (1+r)\mu m)=P((1+r{)}^X\ge (1+r{)}^{(1+r)\mu m})\le \frac{\mathbb{E}[(1+r{)}^X]}{(1+r{)}^{(1+r)\mu m}}$$

由于 $x_i$ 之间是独立的，可得：

$$\mathbb{E}[(1+r{)}^X]=\prod _{i=1}^m\mathbb{E}[(1+r{)}^{x_i}]\le \prod _{i=1}^m\mathbb{E}[1+r{x}_i]\le \prod _{i=1}^m(1+r\mu )\le e^{r\mu m}$$

其中，第二步使用了 $\mathrm{\forall }x\in [0,1]$ 都有 $(1+r{)}^x\le 1+rx$，第三步使用了 $\mathbb{E}[x_i]\le \mu$，第四步使用了 $\mathrm{\forall }x\in [0,1]$ 都有 $1+x\le e^x$。

又由于 $\mathrm{\forall }r\in [0,1]$，有 $\frac{e^r}{(1+r{)}^{1+r}}\le e^{-\frac{r^2}{3}}$，综上所述：

$$P(X\ge (1+r)\mu m)\le (\frac{e^r}{(1+r{)}^{(1+r)}}{)}^{\mu m}\le e^{-\frac{r^2\mu m}{3}}$$

当我们将 $r$ 替换为 $-r$ 时，根据之前的推导，并利用 $\mathrm{\forall }r\in [0,1]$ 有 $\frac{e^r}{(1-r{)}^{1-r}}\le e^{-\frac{r^2}{2}}$，可得第二个不等式的证明。$◻$

1.13 最优 Chernoff 界

如果 $X$ 是一个随机变量，并且 $\mathbb{E}[e^{\lambda (X-\mathbb{E}X)}]\le e^{\varphi (\lambda )}$ 对于所有 $\lambda \ge 0$ 成立，则有以下结论：

$$P(X-\mathbb{E}X\ge \epsilon )\le e^{-{\varphi }^{\ast }(\epsilon )},\epsilon \ge 0$$

或

$$P(X-\mathbb{E}X\le ({\varphi }^{\ast }{)}^{-1}(\ln (1/\delta )))\ge 1-\delta ,\delta \in [0,1]$$

其中，${\varphi }^{\ast }$ 是 $\varphi$ 的凸共轭函数，即 ${\varphi }^{\ast }(x)=\underset{\lambda \ge 0}{sup}(\lambda x-\varphi (\lambda ))$。

证明

根据 Chernoff 不等式，有：

$$\begin{array}{rl}P(X-\mathbb{E}X\ge \epsilon )& \le \underset{\lambda \ge 0}{inf}{e}^{-\lambda \epsilon }\mathbb{E}[e^{\lambda (X-\mathbb{E}X)}]\\ & \le \underset{\lambda \ge 0}{inf}{e}^{\varphi (\lambda )-\lambda \epsilon }\\ & =e^{-\underset{\lambda \ge 0}{sup}(\lambda \epsilon -\varphi (\lambda ))}\\ & =e^{-{\varphi }^{\ast }(\epsilon )}\end{array}$$

因此，最优 Chernoff 界得证。$◻$

1.14 Hoeffding 不等式

设有 $m$ 个独立随机变量 $X_i\in [a_i,b_i]$，令 $\overline{X}$ 为 $X_i$ 的均值。Hoeffding 不等式表示：

$$P(\overline{X}-\mathbb{E}[\overline{X}]\ge \epsilon )\le \exp (-\frac{2m^2{\epsilon }^2}{\sum _{i=1}^m(b_i-a_i{)}^2})$$

证明

首先，我们引入一个引理 (Hoeffding 定理)：

对于 $\mathbb{E}[X]=0$ 且 $X\in [a,b]$ 的随机变量，对于任意 $\lambda \in \mathbb{R}$，有：

$$\mathbb{E}[e^{\lambda X}]\le \exp (\frac{{\lambda }^2(b-a{)}^2}{8})$$

由于 $e^x$ 是凸函数，对于任意 $x\in [a,b]$，可以写为：

$$e^{\lambda x}\le \frac{b-x}{b-a}{e}^{\lambda a}+\frac{x-a}{b-a}{e}^{\lambda b}$$

对上式取期望，得到：

$$\mathbb{E}[e^{\lambda X}]\le \frac{b-\mathbb{E}[X]}{b-a}{e}^{\lambda a}+\frac{\mathbb{E}[X]-a}{b-a}{e}^{\lambda b}=\frac{b{e}^{\lambda a}-a{e}^{\lambda b}}{b-a}$$

记 $\theta =-\frac{a}{b-a}$，$h=\lambda (b-a)$，则：

$$\frac{b{e}^{\lambda a}-a{e}^{\lambda b}}{b-a}=[1-\theta +\theta e^h]e^{-\theta h}=e^{\ln (1-\theta +\theta e^h)}{e}^{-\theta h}=e^{\ln (1-\theta +\theta e^h)-\theta h}$$

定义函数 $\phi (\theta ,h)=\ln (1-\theta +\theta e^h)-\theta h$。注意到 $\theta$ 实际上与 $h$ 无关。对 $h$ 求偏导数：

$$\frac{\partial \phi }{\partial h}=\frac{\theta e^h}{1-\theta +\theta e^h}-\theta$$

显然有 $\frac{\partial \phi }{\partial h}{|}_{h=0^{+}}=0$。同理，利用链式法则可得：

$$\frac{{\partial }^2\phi }{\partial h^2}=\frac{\theta e^h(1-\theta +\theta e^h)-{\theta }^2{e}^{2h}}{(1-\theta +\theta e^h{)}^2}=\frac{\theta e^h}{1-\theta +\theta e^h}(1-\frac{\theta e^h}{1-\theta +\theta e^h})\le \frac{1}{4}$$

根据泰勒展开式，可以得到：

$$\phi (\theta ,h)\le \frac{h^2}{8}=\frac{{\lambda }^2(b-a{)}^2}{8}$$

由 Markov 不等式可知，对于任意 $\lambda >0$：

$$P(\overline{X}-\mathbb{E}[\overline{X}]\ge \epsilon )=P(e^{\lambda (\overline{X}-\mathbb{E}[\overline{X}])}\ge e^{\lambda \epsilon })\le \frac{\mathbb{E}[e^{\lambda (\overline{X}-\mathbb{E}[\overline{X}])}]}{e^{\lambda \epsilon }}$$

利用随机变量的独立性及 Hoeffding 引理，有：

$$\frac{\mathbb{E}[e^{\lambda (\overline{X}-\mathbb{E}[\overline{X}]})]}{e^{\lambda \epsilon }}=e^{-\lambda \epsilon }\prod _{i=1}^m\mathbb{E}[e^{\lambda (X_i-\mathbb{E}[X_i])/m}]\le e^{-\lambda \epsilon }\prod _{i=1}^m\exp (\frac{{\lambda }^2(b_i-a_i{)}^2}{8m^2})$$

考虑二次函数 $g(\lambda )=-\lambda \epsilon +\frac{{\lambda }^2}{8m^2}\sum _{i=1}^m(b_i-a_i{)}^2$，其最小值为 $-\frac{2m^2{\epsilon }^2}{\sum _{i=1}^m(b_i-a_i{)}^2}$。

因此可以得到：

$$P(\overline{X}-\mathbb{E}[\overline{X}]\ge \epsilon )\le \exp (-\frac{2m^2{\epsilon }^2}{\sum _{i=1}^m(b_i-a_i{)}^2})$$

$◻$

注意，这里并未要求随机变量同分布，因此Hoeffding 不等式常用来解释集成学习的基本原理。

1.15 McDiarmid 不等式

对于 $m$ 个独立随机变量 $X_i\in \mathcal{X}$，若函数 $f$ 是差有界的，则对于任意 $\epsilon >0$，有：

$$P(f(X_1,\cdots ,X_m)-\mathbb{E}[f(X_1,\cdots ,X_m)]\ge \epsilon )\le \exp (-\frac{{\epsilon }^2}{2\sum _{i=1}^m{c}_i^2})$$

证明

构造一个鞅差序列：

$$D_j=\mathbb{E}[f(X)\mid X_1,\cdots ,X_j]-\mathbb{E}[f(X)\mid X_1,\cdots ,X_{j-1}]$$

容易验证：

$$f(X)-\mathbb{E}[f(X)]=\sum _{i=1}^m{D}_i$$

由于 $f$ 是差有界的，因此满足 Azuma-Hoeffding 引理。代入后可得：

$$P(f(X_1,\cdots ,X_m)-\mathbb{E}[f(X_1,\cdots ,X_m)]\ge \epsilon )\le \exp (-\frac{{\epsilon }^2}{2\sum _{i=1}^m{c}_i^2})$$

原不等式得证。$◻$

1.16 Bennett 不等式

对于 $m$ 个独立随机变量 $X_i$，令 $\overline{X}$ 为 $X_i$ 的均值，若存在 $b>0$，使得 $|X_i-\mathbb{E}[X_i]|<b$，则有：

$$P(\overline{X}-\mathbb{E}[\overline{X}]\ge \epsilon )\le \exp (-\frac{m{\epsilon }^2}{2(\sum _{i=1}^m\mathbb{V}[X_i]/m+b\epsilon /3)})$$

证明

首先，Bennett 不等式是 Hoeffding 不等式的一个加强版，对于独立随机变量的条件可以放宽为弱独立条件，结论仍然成立。

这些 Bernstein 类的集中不等式更多地反映了在非渐近观点下的大数定律表现，即它们刻画了样本均值如何集中在总体均值附近。

如果将样本均值看作是样本（数据点的函数），即令 $f(X_1,\cdots ,X_m)=\sum _{i=1}^m{X}_i/m$，那么 Bernstein 类不等式刻画了如下的概率：

$$P(f(X_1,\cdots ,X_m)-\mathbb{E}[f(X_1,\cdots ,X_m)]\ge \epsilon )$$

为了在某些泛函上也具有类似 Bernstein 类的集中不等式形式，显然 $f$ 需要满足某些特定性质。差有界性是一种常见的约束条件。

定义 3: 差有界性

函数 $f:{\mathcal{X}}^m\to \mathbb{R}$ 满足对于每个 $i$，存在常数 $c_i<\mathrm{\infty }$，使得：

$$|f(x_1,\cdots ,x_i,\cdots ,x_m)-f(x_1,\cdots ,x_i^{\prime },\cdots ,x_m)|\le c_i$$

则称 $f$ 是差有界的。

为了证明这些结果，需要引入一些新的数学工具。

定义 4: 离散鞅

若离散随机变量序列（随机过程）$Z_m$ 满足：

1. $\mathbb{E}[|Z_i|]<\mathrm{\infty }$
2. $\mathbb{E}[Z_{m+1}\mid Z_1,\cdots ,Z_m]=\mathbb{E}[Z_{m+1}\mid {\mathcal{F}}_m]=Z_m$

则称序列 $Z_i$ 为离散鞅。

引理 2: Azuma-Hoeffding 定理

对于鞅 $Z_i$，若 $\mathbb{E}[Z_i]=\mu ,Z_1={\mu }_{\circ }$，则构造鞅差序列 $X_i=Z_i-Z_{i-1}$，且 $|X_i|\le c_i$，则对于任意 $\epsilon >0$，有：

$$P(Z_m-\mu \ge \epsilon )=P(\sum _{i=1}^m{X}_i\ge \epsilon )\le \exp (-\frac{{\epsilon }^2}{2\sum _{i=1}^m{c}_i^2})$$

证明

首先，若 $\mathbb{E}[X\mid Y]=0$，则有 $\mathrm{\forall }\lambda >0$：

$$\mathbb{E}[e^{\lambda X}\mid Y]\le \mathbb{E}[e^{\lambda X}]$$

因此，由恒等式 $\mathbb{E}[\mathbb{E}[X\mid Y]]=\mathbb{E}[X]$ 及 Chernoff 一般性技巧，对于任意 $\lambda >0$：

$$\begin{array}{rl}P(Z_m-\mu \ge \epsilon )& \ge e^{-\lambda \epsilon }\mathbb{E}[e^{\lambda (Z_m-\mu )}]\\ & =e^{-\lambda \epsilon }\mathbb{E}[\mathbb{E}[e^{\lambda (Z_m-\mu )}\mid {\mathcal{F}}_{m-1}]]\\ & =e^{-\lambda \epsilon }\mathbb{E}[e^{\lambda (Z_{m-1}-\mu )}\mathbb{E}[e^{\lambda (Z_m-Z_{m-1})}\mid {\mathcal{F}}_{m-1}]]\end{array}$$

由于 $\{X_i\}$ 是鞅差序列，因此 $\mathbb{E}[X_m\mid {\mathcal{F}}_{m-1}]=0,\mathbb{E}[X_i]=0$。再结合不等式 $\mathbb{E}[e^{\lambda X}\mid Y]\le \mathbb{E}[e^{\lambda X}]$ 及 Hoeffding 引理，有：

$$\begin{array}{rl}P(Z_m-\mu \ge \epsilon )& \le e^{-\lambda \epsilon }\mathbb{E}[e^{\lambda (Z_{m-1}-\mu )}]\mathbb{E}[e^{\lambda X_n}]\\ & \le e^{-\lambda \epsilon }\mathbb{E}[e^{\lambda (Z_{m-1}-\mu )}]\exp (\frac{{\lambda }^2{c}_m^2}{2})\end{array}$$

迭代上不等式可得：

$$P(Z_m-\mu \ge \epsilon )\le e^{-\lambda \epsilon }\prod _{i=1}^m\exp (\frac{{\lambda }^2{c}_i^2}{2})$$

当 $\lambda =\frac{\epsilon }{\sum _{i=1}^m{c}_i^2}$ 时，上式右端取得极小值：

$$P(Z_m-\mu \ge \epsilon )\le \exp (-\frac{{\epsilon }^2}{2\sum _{i=1}^m{c}_i^2})$$

原不等式得证。$◻$

1.17 Bernstein 不等式

考虑 $m$ 个独立同分布的随机变量 $X_i,i\in [m]$。令 $\overline{X}=\frac{\sum _{i=1}^m{X}_i}{m}$。若存在常数 $b>0$，使得对所有 $k\ge 2$，第 $k$ 阶矩满足 $\mathbb{E}[|X_i{|}^k]\le \frac{k!b^{k-2}}{2}\mathbb{V}[X_1]$，则该不等式成立：

$$\mathbb{P}(\overline{X}\ge \mathbb{E}[\overline{X}]+ϵ)\le \exp \left(\frac{-m{ϵ}^2}{2\mathbb{V}[X_1]+2bϵ}\right)$$

证明

首先，我们需要将矩条件（Moment Condition）转换为亚指数条件（Sub-exponential Condition），以便进一步推导，即：

• 矩条件： 对于随机变量 $X$，其 $k$-阶中心矩 满足如下条件：

  $$\mathbb{E}[|X-\mathbb{E}[X]{|}^k]\le \frac{k!b^{k-2}}{2}\mathbb{V}[X],\mathrm{\forall }k\ge 2$$

  其中：

  1. 中心矩：随机变量 $X$ 的 $k$ 阶中心矩为 $\mathbb{E}[|X-\mathbb{E}[X]{|}^k]$，表示 $X$ 偏离其期望值的 $k$ 次幂的期望值。中心矩用于衡量随机变量的分布形状，尤其是描述其尾部行为。当 $k=2$ 时，中心矩即为随机变量的方差。
  2. $\frac{k!}{2}$ 是阶乘项，随着 $k$ 增大迅速增长。
  3. $b^{k-2}$ 是一个修正因子，其中 $b$ 为常数，用以控制高阶矩的增长速率。
  4. $\mathbb{V}[X]$ 表示随机变量 $X$ 的方差，它作为标准的离散度量来标定中心矩的大小。

• 亚指数条件： 给定随机变量 $X$，其均值为 $\mathbb{E}[X]$，方差为 $\mathbb{V}[X]$，则其偏离均值的随机变量 $X-\mathbb{E}[X]$ 的矩母函数（MGF）满足如下不等式：

  $$\mathbb{E}\left[e^{\lambda (X-\mathbb{E}[X])}\right]\le \exp \left(\frac{\mathbb{V}[X]{\lambda }^2}{2(1-b\lambda )}\right),\mathrm{\forall }\lambda \in [0,\frac{1}{b})$$

  其中：

  1. 矩母函数：这是一个重要的工具，用于控制随机变量的尾部概率。矩母函数的形式是 $\mathbb{E}[e^{\lambda X}]$，它通过调整 $\lambda$ 来捕捉不同程度的偏差行为。
  2. 方差主导项：不等式右边的表达式包含一个方差主导的项 $\frac{\mathbb{V}[X]{\lambda }^2}{2}$，类似于高斯分布的尾部特性，表明当 $\lambda$ 较小时，$X$ 的偏差行为主要由其方差控制，尾部概率呈现指数衰减。
  3. 修正项 $(1-b\lambda )$：该项显示，当 $\lambda$ 接近 $\frac{1}{b}$ 时，尾部偏差的控制变得更加复杂。这种形式通常出现在亚指数条件中，意味着随机变量的尾部行为介于高斯分布和重尾分布之间，尾部衰减较慢但仍比重尾分布快。

---

• 步骤 1：中心化随机变量

设：

$$Y=X-\mathbb{E}[X]$$

我们的目标是对 $Y$ 的矩母函数（MGF）进行上界：

$$\mathbb{E}\left[e^{\lambda Y}\right]$$

---

• 步骤 2：展开指数矩

将 MGF 展开为幂级数（Taylor展开）：

$$\mathbb{E}\left[e^{\lambda Y}\right]=\mathbb{E}\left[\sum _{k=0}^{\mathrm{\infty }}\frac{(\lambda Y{)}^k}{k!}\right]=\sum _{k=0}^{\mathrm{\infty }}\frac{{\lambda }^k}{k!}\mathbb{E}[Y^k]$$

由于 $\mathbb{E}[Y]=0$，故 $k=1$ 项消失：

$$\mathbb{E}\left[e^{\lambda Y}\right]=1+\sum _{k=2}^{\mathrm{\infty }}\frac{{\lambda }^k}{k!}\mathbb{E}[Y^k]$$

---

• 步骤 3：使用矩条件对中心矩进行上界

根据矩条件：

$$\mathbb{E}[|Y{|}^k]\le \frac{k!b^{k-2}}{2}\mathbb{V}[X]$$

因此：

$$|\mathbb{E}[Y^k]|\le \mathbb{E}[|Y{|}^k]\le \frac{k!b^{k-2}}{2}\mathbb{V}[X]$$

---

• 步骤 4：代入 MGF 展开式

将上界代入 MGF 展开式：

$$\mathbb{E}\left[e^{\lambda Y}\right]\le 1+\sum _{k=2}^{\mathrm{\infty }}\frac{{\lambda }^k}{k!}\cdot \frac{k!b^{k-2}}{2}\mathbb{V}[X]=1+\frac{\mathbb{V}[X]}{2}\sum _{k=2}^{\mathrm{\infty }}(b\lambda {)}^{k-2}{\lambda }^2$$

通过令 $j=k-2$ 进行简化：

$$\mathbb{E}\left[e^{\lambda Y}\right]\le 1+\frac{\mathbb{V}[X]{\lambda }^2}{2}\sum _{j=0}^{\mathrm{\infty }}(b\lambda {)}^j$$

---

• 步骤 5：求解几何级数的和

当 $b\lambda <1$ 时，几何级数收敛：

$$\sum _{j=0}^{\mathrm{\infty }}(b\lambda {)}^j=\frac{1}{1-b\lambda }$$

因此：

$$\mathbb{E}\left[e^{\lambda Y}\right]\le 1+\frac{\mathbb{V}[X]{\lambda }^2}{2(1-b\lambda )}$$

---

• 步骤 6：应用指数不等式

使用不等式 $1+x\le e^x$ 对所有实数 $x$ 成立：

$$\mathbb{E}\left[e^{\lambda Y}\right]\le \exp \left(\frac{\mathbb{V}[X]{\lambda }^2}{2(1-b\lambda )}\right)$$

这与亚指数条件相符：

$$\mathbb{E}\left[e^{\lambda Y}\right]\le \exp \left(\frac{\mathbb{V}[X]{\lambda }^2}{2(1-b\lambda )}\right),\mathrm{\forall }\lambda \in [0,\frac{1}{b})$$

---

接下来我们完成在给定矩条件下的Bernstein 不等式的证明，即：

陈述：

给定 $m$ 个独立同分布的随机变量 $X_i,i\in [m]$，令 $\overline{X}=\frac{1}{m}\sum _{i=1}^m{X}_i$。若存在常数 $b>0$，使得对所有 $k\ge 2$，

$$\mathbb{E}[|X_i-\mathbb{E}[X_i]{|}^k]\le \frac{k!b^{k-2}}{2}\mathbb{V}[X_1],$$

则对于任意 $ϵ>0$，

$$\mathbb{P}(\overline{X}\ge \mathbb{E}[\overline{X}]+ϵ)\le \exp \left(\frac{-m{ϵ}^2}{2\mathbb{V}[X_1]+2bϵ}\right)$$

---

• 步骤 1：定义单侧 Bernstein 条件

首先，回顾对于参数 $b>0$ 的单侧 Bernstein 条件：

$$\mathbb{E}\left[e^{\lambda (Y)}\right]\le \exp \left(\frac{\mathbb{V}[Y]{\lambda }^2/2}{1-b\lambda }\right),\mathrm{\forall }\lambda \in [0,\frac{1}{b})$$

其中 $Y=X-\mathbb{E}[X]$。

根据矩条件，我们已经证明 $Y$ 满足亚指数条件：

$$\mathbb{E}\left[e^{\lambda Y}\right]\le \exp \left(\frac{\mathbb{V}[Y]{\lambda }^2}{2(1-b\lambda )}\right),\mathrm{\forall }\lambda \in [0,\frac{1}{b})$$

因此，$Y$ 满足单侧 Bernstein 条件，且 $\mathbb{V}[Y]=\mathbb{V}[X]$。

• 步骤 2：应用 Chernoff 界

考虑 $m$ 个独立同分布随机变量 $Y_i=X_i-\mathbb{E}[X_i]$ 的和：

$$S_m=\sum _{i=1}^m{Y}_i=m(\overline{X}-\mathbb{E}[\overline{X}])$$

我们的目标是对概率 $\mathbb{P}(S_m\ge mϵ)$ 进行上界，这等价于 $\mathbb{P}(\overline{X}\ge \mathbb{E}[\overline{X}]+ϵ)$。

使用Chernoff 界：

$$\mathbb{P}(S_m\ge mϵ)\le \underset{\lambda >0}{inf}\exp (-\lambda mϵ)\mathbb{E}\left[e^{\lambda S_m}\right]$$

• 步骤 3：对和的矩母函数进行上界

由于 $Y_i$ 是独立的：

$$\mathbb{E}\left[e^{\lambda S_m}\right]=\prod _{i=1}^m\mathbb{E}\left[e^{\lambda Y_i}\right]\le {[\exp \left(\frac{\mathbb{V}[Y_i]{\lambda }^2}{2(1-b\lambda )}\right)]}^m=\exp \left(\frac{m\mathbb{V}[Y]{\lambda }^2}{2(1-b\lambda )}\right)$$

因此：

$$\mathbb{P}(S_m\ge mϵ)\le \underset{\lambda >0}{inf}\exp (-\lambda mϵ+\frac{m\mathbb{V}[Y]{\lambda }^2}{2(1-b\lambda )})$$

• 步骤 4：对 $\lambda$ 进行优化

为了找到最紧的界，我们需要对 $\lambda$ 进行优化。最优的 $\lambda$ 是使指数最小的值：

$$-\lambda mϵ+\frac{m\mathbb{V}[Y]{\lambda }^2}{2(1-b\lambda )}$$

对 $\lambda$ 求导并令其为零：

$$-ϵ+\frac{\mathbb{V}[Y]\lambda }{1-b\lambda }+\frac{\mathbb{V}[Y]{\lambda }^{2}b}{2(1-b\lambda {)}^2}=0$$

然而，直接求解该方程较为复杂。我们可以选择：

$$\lambda =\frac{ϵ}{\mathbb{V}[Y]+bϵ}$$

此时 $\lambda$ 满足 $[0,\frac{1}{b})$ 的范围，因为：

$$\lambda b=\frac{bϵ}{\mathbb{V}[Y]+bϵ}<1$$

• 步骤 5：将最优的 $\lambda$ 代入界中

将 $\lambda =\frac{ϵ}{\mathbb{V}[Y]+bϵ}$ 代入指数中：

$$-\lambda mϵ+\frac{m\mathbb{V}[Y]{\lambda }^2}{2(1-b\lambda )}=-\frac{m{ϵ}^2}{\mathbb{V}[Y]+bϵ}+\frac{m\mathbb{V}[Y]{\left(\frac{ϵ}{\mathbb{V}[Y]+bϵ}\right)}^2}{2(1-\frac{bϵ}{\mathbb{V}[Y]+bϵ})}$$

在第二项中简化分母：

$$1-b\lambda =1-\frac{bϵ}{\mathbb{V}[Y]+bϵ}=\frac{\mathbb{V}[Y]}{\mathbb{V}[Y]+bϵ}$$

现在，代入回去：

$$-\frac{m{ϵ}^2}{\mathbb{V}[Y]+bϵ}+\frac{m{ϵ}^2}{2(\mathbb{V}[Y]+bϵ)}=-\frac{m{ϵ}^2}{2(\mathbb{V}[Y]+bϵ)}$$

因此：

$$\mathbb{P}(S_m\ge mϵ)\le \exp (-\frac{m{ϵ}^2}{2(\mathbb{V}[Y]+bϵ)})$$

• 步骤 6：回到样本均值

回忆：

$$S_m=m(\overline{X}-\mathbb{E}[\overline{X}])$$

因此：

$$\mathbb{P}(\overline{X}-\mathbb{E}[\overline{X}]\ge ϵ)=\mathbb{P}(S_m\ge mϵ)\le \exp (-\frac{m{ϵ}^2}{2(\mathbb{V}[Y]+bϵ)})$$

由于 $\mathbb{V}[Y]=\mathbb{V}[X]$，我们得到：

$$\mathbb{P}(\overline{X}\ge \mathbb{E}[\overline{X}]+ϵ)\le \exp (-\frac{m{ϵ}^2}{2(\mathbb{V}[X]+bϵ)})$$

$◻$

1.18 Azuma–Hoeffding（Azuma）不等式

对于均值为 $Z_0=\mu$ 的鞅差序列 $\{Z_m,m\ge 1\}$，若 $|Z_i-Z_{i-1}|\le c_i$，其中$c_i>0$为已知常数，则对于任意 $\epsilon >0$，有：

$$\begin{array}{rl}P(Z_m-\mu \ge \epsilon )& \le \exp (-\frac{{\epsilon }^2}{2\sum _{i=1}^m{c}_i^2})\\ P(Z_m-\mu \le -\epsilon )& \le \exp (-\frac{{\epsilon }^2}{2\sum _{i=1}^m{c}_i^2})\end{array}$$

证明

1. 构造指数鞅

   考虑参数 $s>0$，构造如下的指数鞅：

   $$M_m=\exp (s(Z_m-\mu )-\frac{s^2}{2}\sum _{i=1}^m{c}_i^2)$$

   我们需要证明 $\{M_m{\}}_{m\ge 0}$ 是一个超鞅。

2. 验证鞅性质

   对于任意 $m\ge 1$，有

   $$\mathbb{E}[M_m\mid {\mathcal{F}}_{m-1}]=\mathbb{E}[\exp (s(Z_m-Z_{m-1}))\mid {\mathcal{F}}_{m-1}]\cdot \exp (s(Z_{m-1}-\mu )-\frac{s^2}{2}\sum _{i=1}^m{c}_i^2)$$

   由于 $|Z_m-Z_{m-1}|\le c_m$，并且 $\mathbb{E}[Z_m-Z_{m-1}\mid {\mathcal{F}}_{m-1}]=0$（鞅性质），可以应用 Hoeffding 引理得到：

   $$\mathbb{E}[\exp (s(Z_m-Z_{m-1}))\mid {\mathcal{F}}_{m-1}]\le \exp (s\mathbb{E}[Z_m-Z_{m-1}\mid {\mathcal{F}}_{m-1}]+\frac{s^2(c_m-(-c_m){)}^2}{8})=\exp (\frac{s^2{c}_m^2}{2})$$

   因此，

   $$\mathbb{E}[M_m\mid {\mathcal{F}}_{m-1}]\le \exp (\frac{s^2{c}_m^2}{2})\cdot \exp (s(Z_{m-1}-\mu )-\frac{s^2}{2}\sum _{i=1}^m{c}_i^2)=M_{m-1}$$

   这表明 $\{M_m\}$ 是一个超鞅。

3. 应用鞅不等式

   由于 $\{M_m\}$ 是一个超鞅，且 $M_0=\exp (0)=1$，根据超鞅的性质，有

   $$\mathbb{E}[M_m]\le M_0=1$$

   对于事件 $\{Z_m-\mu \ge \epsilon \}$，有

   $$M_m=\exp (s(Z_m-\mu )-\frac{s^2}{2}\sum _{i=1}^m{c}_i^2)\ge \exp (s\epsilon -\frac{s^2}{2}\sum _{i=1}^m{c}_i^2)$$

   我们令 $a=\exp (s\epsilon -\frac{s^2}{2}\sum _{i=1}^m{c}_i^2)$，由于 $\{Z_m-\mu \ge \epsilon \}$ 蕴含了 $\{M_m\ge a\}$，所以：

   $$P(Z_m-\mu \ge \epsilon )\le P(M_m\ge a)$$

   结合已知的 $\mathbb{E}[M_m]\le 1$，应用 Markov 不等式可得：

   $$P(M_m\ge a)\le \frac{1}{a}=\exp (-s\epsilon +\frac{s^2}{2}\sum _{i=1}^m{c}_i^2)$$

   因此，我们得到：

   $$P(Z_m-\mu \ge \epsilon )\le \exp (-s\epsilon +\frac{s^2}{2}\sum _{i=1}^m{c}_i^2)$$

4. 优化参数 $s$

   为了得到最优的上界，选择 $s$ 使得表达式 $-s\epsilon +\frac{s^2}{2}\sum c_i^2$ 最小化。对 $s$ 求导并取零：

   $$-\epsilon +s\sum _{i=1}^m{c}_i^2=0\Rightarrow s=\frac{\epsilon }{\sum _{i=1}^m{c}_i^2}$$

   代入得：

   $$P(Z_m-\mu \ge \epsilon )\le \exp (-\frac{{\epsilon }^2}{2\sum _{i=1}^m{c}_i^2})$$

   这即是 Azuma 不等式的上侧不等式。

5. 下侧不等式的证明

   对于下侧不等式，可以类似地考虑 $-Z_m$ 作为鞅，应用相同的方法得到：

   $$P(Z_m-\mu \le -\epsilon )\le \exp (-\frac{{\epsilon }^2}{2\sum _{i=1}^m{c}_i^2})$$

   因此，Azuma 不等式得证。$◻$

1.19 Slud 不等式

若 $X\sim B(m,p)$，则有：

$$P(\frac{X}{m}\ge \frac{1}{2})\ge \frac{1}{2}[1-\sqrt{1-\exp (-\frac{m{\epsilon }^2}{1-{\epsilon }^2})}]$$

其中 $p=\frac{1-\epsilon }{2}$。

证明

二项随机变量 $X$ 表示在 $m$ 次独立伯努利试验中成功的次数，成功概率为 $p$。对于大的 $m$，二项分布 $B(m,p)$ 可以近似为均值 $\mu =mp$ 和方差 ${\sigma }^2=mp(1-p)$ 的正态分布：

$$\begin{array}{rl}\mu & =\frac{m(1-\epsilon )}{2}\\ {\sigma }^2& =\frac{m(1-{\epsilon }^2)}{4}\end{array}$$

令 $Z=\frac{X-\mu }{\sigma }$，代入 $\mu$ 和 $\sigma$，有：

$$P[\frac{X}{m}\ge \frac{1}{2}]=P[Z\ge \frac{\frac{m}{2}-\mu }{\sigma }]=P[Z\ge \frac{\epsilon \sqrt{m}}{\sqrt{1-{\epsilon }^2}}]$$

根据正态分布不等式（定理 21），有：

$$P[Z\ge x]\ge \frac{1}{2}[1-\sqrt{1-\exp (-\frac{2x^2}{\pi })}]\ge \frac{1}{2}[1-\sqrt{1-\exp (-x^2)}]$$

代入可得：

$$P[Z\ge \frac{\epsilon \sqrt{m}}{\sqrt{1-{\epsilon }^2}}]\ge \frac{1}{2}[1-\sqrt{1-\exp (-\frac{m{\epsilon }^2}{1-{\epsilon }^2})}]$$

$◻$

1.20 上界不等式之加性公式

若 $sup(f)$ 和 $sup(g)$ 分别为函数 $f$ 和 $g$ 的上界，则有：

$$sup(f+g)\le sup(f)+sup(g)$$

证明

假设 $f,g$ 分别有相同的定义域 $D_f,D_g$。根据上确界的定义，对于每一个 $x\in D_f\cap D_g$，我们有

$$g(x)\le \underset{y\in D_g}{sup}g(y),$$

从而

$$f(x)+g(x)\le f(x)+\underset{y\in D_g}{sup}g(y).$$

因为这对于每一个 $x\in D_f\cap D_g$ 都成立，我们可以在不等式的两边取上确界，得到：

$$\underset{x\in D_f\cap D_g}{sup}(f(x)+g(x))\le \underset{x\in D_f\cap D_g}{sup}f(x)+\underset{y\in D_g}{sup}g(y)\le \underset{z\in D_f}{sup}f(z)+\underset{y\in D_g}{sup}g(y).$$

这里我们使用了 $\underset{x\in D_f\cap D_g}{sup}f(x)\le \underset{z\in D_f}{sup}f(z)$，因为 $D_f\cap D_g\subset D_f$。$◻$

值得注意的是，该不等式在（4.33）中利用过两次，且原推导并没有用到 Jensen 不等式的任何性质。

另外，加性公式有几个常见的变形，例如：

$$sup(f-g)-sup(f-k)\le sup(k-g)$$

该不等式在（4.29）中出现过。

1.21 正态分布不等式

若 $X$ 是一个服从标准正态分布的随机变量，那么对于任意 $u\ge 0$，有：

$$\mathbb{P}[X\le u]\le \frac{1}{2}\sqrt{1-e^{-\frac{2}{\pi }{u}^2}}$$

证明

令 $G(u)=\mathbb{P}[X\le u]$，则有：

$$2G(u)={\int }_{-u}^u(2\pi {)}^{-1/2}{e}^{-x^2/2}dx={\int }_{-u}^u(2\pi {)}^{-1/2}{e}^{-y^2/2}dy$$

因此：

$$2\pi [2G(u){]}^2={\int }_{-u}^u{\int }_{-u}^u{e}^{-(x^2+y^2)/2}dxdy$$

让我们考虑更一般的积分形式：

$$2\pi [2G(u){]}^2={\iint }_R{e}^{-(x^2+y^2)/2}dxdy$$

此时 $R$ 为任意面积为 $4u^2$ 的区域。通过反证法可以证明，只有当 $R$ 为以原点为中心的圆形区域 $R_0$ 时，积分值最大：

$$R_0=\{(x,y):\pi (x^2+y^2)\le 4u^2\}$$

此时，有：

$$\begin{array}{rl}2\pi [2G(u){]}^2& \le {\iint }_{R_0}{e}^{-(x^2+y^2)/2}dxdy\\ & ={\int }_0^{2\pi }{\int }_0^{2u{\pi }^{-1/2}}{e}^{-r^2/2}rdrd\phi \\ & =2\pi (1-e^{-2u^2/\pi })\end{array}$$

因此，有：

$$G(u)=\mathbb{P}[X\le u]\le \frac{1}{2}\sqrt{1-e^{-\frac{2}{\pi }{u}^2}}$$

进一步，我们可以得到：

$$\mathbb{P}[X\ge u]\ge \frac{1}{2}(1-\sqrt{1-e^{-\frac{2}{\pi }{u}^2}})$$

$◻$

1.22 AM-GM 不等式

算术平均数和几何平均数的不等式，简称 AM-GM 不等式。该不等式指出非负实数序列的算术平均数大于等于该序列的几何平均数，当且仅当序列中的每个数相同时，等号成立。形式上，对于非负实数序列 $\{x_n\}$，其算术平均值定义为：

$$A_n=\frac{1}{n}\sum _{i=1}^n{x}_i$$

其几何平均值定义为：

$$G_n=\sqrt[n]{\prod _{i=1}^n{x}_i}$$

则 AM-GM 不等式成立：

$$A_n\ge G_n$$

证明

我们可以通过 Jensen 不等式来证明 AM-GM 不等式。首先，我们考虑函数 $f(x)=-\ln x$，该函数是凸函数，因此有：

$$\frac{1}{n}\sum _{i=1}^n-\ln x_i\ge -\ln (\frac{1}{n}\sum _{i=1}^n{x}_i)$$

即：

$$\begin{array}{rl}\ln (\frac{1}{n}\sum _{i=1}^n{x}_i)& \ge \frac{1}{n}\sum _{i=1}^n\ln x_i=\ln (\sqrt[n]{\prod _{i=1}^n{x}_i})\\ \Rightarrow \frac{1}{n}\sum _{i=1}^n{x}_i& \ge \sqrt[n]{\prod _{i=1}^n{x}_i}\end{array}$$

当取 $x_1=x_2=\cdots =x_n$ 时，等号成立。特别地，当 $n=2$ 时，我们有：

$$\frac{x_1+x_2}{2}\ge \sqrt{x_1{x}_2}$$

$◻$

1.23 Young 不等式

对于任意 $a,b\ge 0$ 且 $p,q>1$，若 $\frac{1}{p}+\frac{1}{q}=1$，则有：

$$ab\le \frac{a^p}{p}+\frac{b^q}{q}$$

当且仅当 $a^p=b^q$ 时，等号成立。

证明

我们可以通过 Jensen 不等式来证明 Young 不等式。首先，当 $ab=0$ 时，该不等式显然成立。当 $a,b>0$ 时，我们令 $t=1/p,1-t=1/q$，根据 $\ln (x)$ 的凹性，我们有：

$$\begin{array}{rl}\ln (t{a}^p+(1-t)b^q)& \ge t\ln (a^p)+(1-t)\ln (b^q)\\ & =\ln (a)+\ln (b)\\ & =\ln (ab)\end{array}$$

当且仅当 $a^p=b^q$ 时，等号成立。$◻$

1.24 Bayes 定理

贝叶斯定理是概率论中的一个重要定理，它描述了在已知某些条件下更新事件概率的数学方法。贝叶斯定理的公式为：

$$P(A|B)=\frac{P(B|A)\cdot P(A)}{P(B)}$$

其中：

• $P(A|B)$ 是在事件 B 发生的情况下事件 A 发生的后验概率。
• $P(B|A)$ 是在事件 A 发生的情况下事件 B 发生的似然函数。
• $P(A)$ 是事件 A 的先验概率。
• $P(B)$ 是事件 B 的边缘概率。

证明

根据条件概率的定义，事件 A 在事件 B 发生下的条件概率 $P(A|B)$ 表示为：

$$P(A|B)=\frac{P(A\cap B)}{P(B)}$$

同样地，事件 B 在事件 A 发生下的条件概率 $P(B|A)$ 表示为：

$$P(B|A)=\frac{P(A\cap B)}{P(A)}$$

通过这两个公式可以得到联合概率 $P(A\cap B)$ 的两种表示方式：

$$P(A\cap B)=P(A|B)\cdot P(B)$$

以及：

$$P(A\cap B)=P(B|A)\cdot P(A)$$

由于联合概率的性质，我们可以将上述两个等式等同：

$$P(A|B)\cdot P(B)=P(B|A)\cdot P(A)$$

将上述等式两边同时除以 $P(B)$，得到贝叶斯定理：

$$P(A|B)=\frac{P(B|A)\cdot P(A)}{P(B)}$$

$◻$

通过先验和后验的更新过程，贝叶斯统计提供了一种动态的、不断修正认知的不确定性量化方法。

1.25 广义二项式定理

广义二项式定理（Generalized Binomial Theorem）是二项式定理的扩展：

$$(x+y{)}^r=\sum _{k=0}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{r}{k})x^{r-k}{y}^k,|x|<|y|,k\in \mathbb{N},r\in \mathbb{R}$$

其中我们令 $(\genfrac{}{}{0ex}{}{r}{k}):=\frac{(r{)}_k}{k!}$，$(r{)}_k=r(r-1)\cdots (r-k+1)$ 为递降阶乘（falling factorial）。

证明

首先代入定义，易证：

$$(r-k)(\genfrac{}{}{0ex}{}{r}{k})+(r-(k-1))(\genfrac{}{}{0ex}{}{r}{k-1})=r(\genfrac{}{}{0ex}{}{r}{k})$$

我们从特殊情况 $y=1$ 开始。首先我们证明只要 $|x|<1$，后者级数就会收敛。

通过使用幂级数收敛半径的商式来证明这一点，由于绝对值的连续性使我们可以先在绝对值内部计算极限，可得：

$$\underset{k\to \mathrm{\infty }}{lim}\frac{|a_k|}{|a_{k+1}|}=\underset{k\to \mathrm{\infty }}{lim}|\frac{k+1}{r-k}|=|-1|=1$$

因此我们有一个为 1 的收敛半径。这种收敛使我们能够在 $|x|<1$ 的收敛区域内应用逐项求导，得到：

$$\frac{d}{dx}\sum _{k=0}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{r}{k})x^k=\sum _{k=1}^{\mathrm{\infty }}(r-(k-1))(\genfrac{}{}{0ex}{}{r}{k-1})x^{k-1}$$

如果我们将我们正在考虑的级数定义的函数记为 $g(x)$，我们得到：

$$\begin{array}{rl}(1+x)\frac{d}{dx}g(x)& =\sum _{k=1}^{\mathrm{\infty }}(r-(k-1))(\genfrac{}{}{0ex}{}{r}{k-1})x^{k-1}+\sum _{k=1}^{\mathrm{\infty }}(r-(k-1))(\genfrac{}{}{0ex}{}{r}{k-1})x^k\\ & =r+\sum _{k=1}^{\mathrm{\infty }}((r-k)(\genfrac{}{}{0ex}{}{r}{k})+(r-(k-1))(\genfrac{}{}{0ex}{}{r}{k-1}))x^k\\ & =r+r\sum _{k=1}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{r}{k})x^k\\ & =rg(x),\end{array}$$

上式的推导使用了前述引理。

现在定义 $f(x)=(1+x{)}^r$，我们通过通常的求导规则得到：

$$\frac{d}{dx}(\frac{g(x)}{f(x)})=\frac{g^{\prime }(x)f(x)-f^{\prime }(x)g(x)}{f(x{)}^2}=\frac{r\frac{g(x)}{x+1}(1+x{)}^r-rg(x)(1+x{)}^{r-1}}{f(x{)}^2}=0$$

$|x|<1$ 意味着 $f(x)\ne 0$，因此 $g/f$ 为常数。又 $f(0)=g(0)=1$ 可得 $f(x)=g(x)$。

对于一般的 $x,y\in \mathbb{R}$ 且 $|x|<|y|$，我们有：

$$\frac{(x+y{)}^r}{y^r}=(\frac{x}{y}+1{)}^r=\sum _{k=0}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{r}{k})(\frac{x}{y}{)}^k;$$

收敛性由假设 $|x/y|<1$ 保证。为了得到原定理的形式，我们只需乘以 $y^r$ 即可。$◻$

1.26 Stirling 公式

Stirling 公式是用于近似计算阶乘的一种公式，即使在 $n$ 很小时也有很高的精度。Stirling 公式的一种形式为：

$$n!=\sqrt{2\pi }{n}^{n+1/2}{e}^{-n}{e}^{r_n}$$

其中，$\frac{1}{12n+1}<r_n<\frac{1}{12n}$。

证明

我们令：

$$S_n=\ln (n!)=\sum _{p=1}^{n-1}\ln (p+1)$$

且

$$\ln (p+1)=A_p+b_p-{\epsilon }_p$$

其中：

$$\begin{array}{rl}{A}_p& ={\int }_p^{p+1}\ln xdx\\ b_p& =\frac{1}{2}[\ln (p+1)-\ln (p)]\\ {\epsilon }_p& ={\int }_p^{p+1}\ln xdx-\frac{1}{2}[\ln (p+1)+\ln (p)]\end{array}$$

此时：

$$S_n=\sum _{p=1}^{n-1}(A_p+b_p-{\epsilon }_p)={\int }_1^n\ln xdx+\frac{1}{2}\ln n-\sum _{p=1}^{n-1}{\epsilon }_p$$

易证 $\int \ln xdx=x\ln x-x+C,C\in \mathbb{R}$，故：

$$S_n=(n+1/2)\ln n-n+1-\sum _{p=1}^{n-1}{\epsilon }_p$$

此时：

$${\epsilon }_p=\frac{2p+1}{2}\ln (\frac{p+1}{p})-1$$

接下来我们对 $\ln (\frac{p+1}{p})$ 进行级数展开，根据广义二项式定理，即：

令 $a=-1,t=\frac{1}{p},t\in (-1,1)$，则有：

$$\frac{1}{1+t}=1-t+t^2-t^3+t^4-\cdots$$

对上式两边同时进行积分，我们有：

$$\ln (1+t)=t-\frac{1}{2}{t}^2+\frac{1}{3}{t}^3-\frac{1}{4}{t}^4+\cdots$$

如果我们令 $-t$ 来代替 $t$，则有：

$$\ln \frac{1}{1-t}=t+\frac{1}{2}{t}^2+\frac{1}{3}{t}^3+\frac{1}{4}{t}^4+\cdots$$

将两式相加，我们有：

$$\frac{1}{2}\ln \frac{1+t}{1-t}=t+\frac{1}{3}{t}^3+\frac{1}{5}{t}^5+\cdots$$

回到我们的问题，我们令 $t=(2p+1{)}^{-1}\in (0,1)$，如此才满足 $\frac{1+t}{1-t}=\frac{p+1}{p}$，带入前式：

$${\epsilon }_p=\frac{1}{3(2p+1{)}^2}+\frac{1}{5(2p+1{)}^4}+\frac{1}{7(2p+1{)}^6}+\cdots$$

因此：

$${\epsilon }_p<\frac{1}{3(2p+1{)}^2}\sum _{i=0}^{\mathrm{\infty }}\frac{1}{(2p+1{)}^{2i}}=\frac{1}{3(2p+1{)}^2}\frac{1}{1-\frac{1}{(2p+1{)}^2}}=\frac{1}{3[(2p+1{)}^2-1]}=\frac{1}{12}(\frac{1}{p}-\frac{1}{p+1})$$

且

$${\epsilon }_p>\frac{1}{3(2p+1{)}^2}\sum _{i=0}^{\mathrm{\infty }}\frac{1}{[3(2p+1{)}^2{]}^i}=\frac{1}{3(2p+1{)}^2}\frac{1}{1-\frac{1}{3(2p+1{)}^2}}=\frac{1}{3(2p+1{)}^2-1}$$

易证

$$(p+\frac{1}{12})(p+1+\frac{1}{12})=p^2+\frac{7}{6}p+\frac{13}{144}>p^2+p+\frac{1}{6}=\frac{1}{12}[3(2p+1{)}^2-1],p\in {\mathbb{N}}^{+}$$

因此：

$${\epsilon }_p>\frac{1}{12}(\frac{1}{p+\frac{1}{12}}-\frac{1}{p+1+\frac{1}{12}})$$

我们令：

$$B=\sum _{p=1}^{\mathrm{\infty }}{\epsilon }_p,r_n=\sum _{p=n}^{\mathrm{\infty }}{\epsilon }_p$$

那么易得：

$$\frac{1}{13}<B<\frac{1}{12},\frac{1}{12(n+1)}<r_n<\frac{1}{12n}$$

带入 $S_n$ 的表达式：

$$S_n=(n+\frac{1}{2})\ln n-n+1-B+r_n$$

可得：

$$n!=e^{1-B}{n}^{n+1/2}{e}^{-n}{e}^{r_n}$$

令 $C=e^{1-B}$，我们可知常数 $C$ 的取值范围为 $(e^{11/12},e^{12/13})$，此处我们取 $C=\sqrt{2\pi }$，该公式得证。$◻$

1.27 散度定理

散度定理（Divergence Theorem），也称为高斯定理（Gauss's Theorem），是向量分析中的重要定理，它将体积积分和曲面积分联系起来。

具体而言，如果考虑一个 $n$-维球体（$n$-ball）$B^n$ 的体积为 $V$，其表面为 $S^{n-1}$，对于一个位于 $n$-维空间中的光滑向量场 $\mathbf{F}$，则有：

$${\int }_{B^n}(\mathrm{\nabla }\cdot \mathbf{F})dV={\oint }_{S^{n-1}}\mathbf{F}\cdot \mathbf{n}dS$$

其中：

• $\mathrm{\nabla }\cdot \mathbf{F}$ 是向量场 $\mathbf{F}$ 的散度。
• $dV$ 是体积元素。
• $dS$ 是边界表面的面积元素。
• $\mathbf{n}$ 是边界的单位外法向量。

体积积分计算的是在 $n$-球内的散度，而表面积分计算的是在 $n-1$ 维球面上的通量。 这种形式的散度定理在物理学和工程学中广泛应用，比如电磁学中的高斯定理、流体力学中的质量守恒等。

1.28 分离超平面定理

如果有两个不相交的非空凸集，则存在一个超平面能够将它们完全分隔开，这个超平面叫做分离超平面（Separating Hyperplane）。形式上，设 $A$ 和 $B$ 是 ${\mathbb{R}}^n$ 中的两个不相交的非空凸集，那么存在一个非零向量 $v$ 和一个实数 $c$，使得：

$$⟨x,v⟩\ge c\text{且}⟨y,v⟩\le c$$

对所有 $x\in A$ 和 $y\in B$ 都成立。即超平面 $⟨\cdot ,v⟩=c$ 以 $v$ 作为分离轴（Separating Axis），将 $A$ 和 $B$ 分开。

进一步，如果这两个集合都是闭集，并且至少其中一个是紧致的，那么这种分离可以是严格的，即存在 $c_1>c_2$ 使得：

$$⟨x,v⟩>c_1\text{且}⟨y,v⟩<c_2$$

在不同情况下，我们可以通过调整 $v$ 和 $c$ 来使得分离超平面的边界更加清晰。

A	B	$⟨x,v⟩$	$⟨y,v⟩$
闭紧集	闭集	$>c_1$	$<c_2$ 且 $c_2<c_1$
闭集	闭紧集	$>c_1$	$<c_2$ 且 $c_2<c_1$
开集	闭集	$>c$	$\le c$
开集	开集	$>c$	$<c$

在支持向量机的背景下，最佳分离超平面（或最大边缘超平面）是分离两个点凸包并且与两者等距的超平面。

证明

证明基于以下引理：

设 $A$ 和 $B$ 是 ${\mathbb{R}}^n$ 中两个不相交的闭集，且假设 $A$ 是紧致的。则存在点 $a_0\in A$ 和 $b_0\in B$ 使得 $\parallel a-b\parallel$ 在 $a\in A$ 和 $b\in B$ 之间取最小值。

我们给出引理的证明：

令 $a\in A$ 和 $b\in B$ 是任意一对点，并令 $r_1=\parallel b-a\parallel$。由于 $A$ 是紧致的，它被包含在以 $a$ 为中心的一些球中，设该球的半径为 $r_2$。令 $S=B\cap \overline{B_{r_1+r_2}(a)}$ 为 $B$ 与以 $a$ 为中心、半径为 $r_1+r_2$ 的闭球的交集。那么 $S$ 是紧致且非空的，因为它包含 $b$。由于距离函数是连续的，存在点 $a_0$ 和 $b_0$ 使得 $\parallel a_0-b_0\parallel$ 在所有 $A\times S$ 的点对中取最小值。现在要证明 $a_0$ 和 $b_0$ 实际上在所有 $A\times B$ 的点对中具有最小距离。假设存在点 $a^{\prime }$ 和 $b^{\prime }$ 使得 $\parallel a^{\prime }-b^{\prime }\parallel <\parallel a_0-b_0\parallel$。则特别地，$\parallel a^{\prime }-b^{\prime }\parallel <r_1$，并且根据三角不等式，$\parallel a-b^{\prime }\parallel \le \parallel a-a^{\prime }\parallel +\parallel a^{\prime }-b^{\prime }\parallel <r_1+r_2$。因此 $b^{\prime }$ 包含在 $S$ 中，这与 $a_0$ 和 $b_0$ 在 $A\times S$ 中的最小距离相矛盾。

不失一般性地，假设 $A$ 是紧致的。根据引理，存在点 $a_0\in A$ 和 $b_0\in B$ 使得它们之间的距离最小。由于 $A$ 和 $B$ 是不相交的，我们有 $a_0\ne b_0$。现在，构造两条与线段 $[a_0,b_0]$ 垂直的超平面 $L_A,L_B$，其中 $L_A$ 穿过 $a_0$，$L_B$ 穿过 $b_0$。我们声称 $A$ 和 $B$ 都没有进入 $L_A,L_B$ 之间的空间，因此与 $(a_0,b_0)$ 垂直的超平面满足定理的要求。

代数上，超平面 $L_A,L_B$ 由向量 $v:=b_0-a_0$ 定义，并由两个常数 $c_A:=⟨v,a_0⟩<c_B:=⟨v,b_0⟩$ 确定，使得 $L_A=\{x:⟨v,x⟩=c_A\},L_B=\{x:⟨v,x⟩=c_B\}$。我们的主张是 $\mathrm{\forall }a\in A,⟨v,a⟩\le c_A$ 并且 $\mathrm{\forall }b\in B,⟨v,b⟩\ge c_B$。

假设存在某个 $a\in A$ 使得 $⟨v,a⟩>c_A$，则令 $a^{\prime }$ 为从 $b_0$ 到线段 $[a_0,a]$ 的垂足。由于 $A$ 是凸集，$a^{\prime }$ 在 $A$ 内部，并且根据平面几何，$a^{\prime }$ 比 $a_0$ 更接近 $b_0$，这与 $a_0$ 和 $b_0$ 的最小距离相矛盾。类似的论证适用于 $B$。$◻$

1.29 支撑超平面定理

对于一个凸集，支撑超平面（Supporting Hyperplane）是与凸集边界切线的超平面，即它“支撑”了凸集，使得所有的凸集内的点都位于支撑超平面的一侧。形式上，若 $S$ 是非空凸集，且 $x_0$ 是 $S$ 的边界上的一点，那么存在一个包含 $x_0$ 的支撑超平面。 如果 $x^{\ast }\in X^{\ast }\mathrm{\setminus }\{0\}$（$X^{\ast }$ 是 $X$ 的对偶空间，$x^{\ast }$ 是一个非零的线性泛函），并且对于所有 $x\in S$ 都有 $x^{\ast }(x_0)\ge x^{\ast }(x)$，那么 $H=\{x\in X:x^{\ast }(x)=x^{\ast }(x_0)\}$ 定义了一个支撑超平面。

证明

定义 $T$ 为所有支撑闭合半空间的交集，显然 $S\subset T$。现在令 $y\notin S$，证明 $y\notin T$。

设 $x\in \mathrm{int}(S)$，并考虑线段 $[x,y]$。令 $t$ 为最大的数，使得 $[x,t(y-x)+x]$ 被包含在 $S$ 中。则 $t\in (0,1)$。令 $b=t(y-x)+x$，那么 $b\in \partial S$。在 $b$ 处画一条支撑超平面，令其表示为一个非零线性泛函 $f:{\mathbb{R}}^n\to \mathbb{R}$，使得 $\mathrm{\forall }a\in T,f(a)\ge f(b)$。由于 $x\in \mathrm{int}(S)$，我们有 $f(x)>f(b)$。因此，由 $\frac{f(y)-f(b)}{1-t}=\frac{f(b)-f(x)}{t-0}<0$，我们得到 $f(y)<f(b)$，所以 $y\notin T$。$◻$