不等式

类别一：基本不等式（基于单调性）

这些不等式最基础，通常不提供具体的数值界限，而是用于建立变量间的大小关系。

1. 马尔可夫不等式

• 陈述：对于非负随机变量 $X \ge 0$ 且 $\mathbb{E}[X] < \infty$，对任意 $t > 0$：

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

• 证明思路： 定义指示函数 $\mathbb{I}_{X \ge t}$。由于 $X \ge 0$，显然有：

  \[X \ge t \cdot \mathbb{I}_{X \ge t}\]

  两边取期望（利用期望的单调性）：

  \[\mathbb{E}[X] \ge t \cdot \mathbb{E}[\mathbb{I}_{X \ge t}] = t \cdot P(X \ge t)\]

  整理即得证。

• 意义：为非负随机变量提供了一个非常宽松的上尾概率界。它只使用了非负性和期望值。

2. 切比雪夫不等式

• 陈述：对于随机变量 $X$ 且 $\text{Var}(X) < \infty$，对任意 $t > 0$：

  \[P(|X - \mathbb{E}[X]| \ge t) \le \frac{\text{Var}(X)}{t^2}\]

• 证明思路： 将马尔可夫不等式应用于非负随机变量 $(X - \mathbb{E}[X])^2$ 和阈值 $t^2$：

  \[P(|X - \mathbb{E}[X]| \ge t) = P((X - \mathbb{E}[X])^2 \ge t^2) \le \frac{\mathbb{E}[(X - \mathbb{E}[X])^2]}{t^2} = \frac{\text{Var}(X)}{t^2}\]

• 意义：提供了围绕均值的偏差概率界，比马尔可夫紧，因为它利用了方差信息。但它给出的仍然是多项式衰减的界 $O(1/t^2)$。

---

类别二：指数浓度不等式

这类不等式能提供指数衰减的尾概率界，远强于切比雪夫不等式。它们通常要求随机变量是独立且有界的。

3. 霍夫丁不等式

• 陈述：设 $X_1, \dots, X_n$ 独立，且 $a_i \le X_i \le b_i$。令 $S_n = \sum_{i=1}^n X_i$。则对任意 $t > 0$：

  \(P(S_n - \mathbb{E}[S_n] \ge t) \le \exp\left( -\frac{2t^2}{\sum_{i=1}^n (b_i - a_i)^2} \right)\) （下尾和双边界类似）

• 证明思路（核心）：
  1. 切尔诺夫界限：$P(Z \ge t) \le e^{-\lambda t} \mathbb{E}[e^{\lambda Z}]$，对 $\lambda > 0$。
  2. 霍夫丁引理：如果 $\mathbb{E}[X]=0$ 且 $a \le X \le b$，则 $\mathbb{E}[e^{\lambda X}] \le \exp(\lambda^2 (b-a)^2 / 8)$。
  3. 串联：将切尔诺夫界限应用于 $Z = S_n - \mathbb{E}[S_n]$，利用独立性分解矩母函数，对每一项应用霍夫丁引理，最后优化 $\lambda$ 得到最紧界。
• 意义：无分布的指数浓度界，只依赖变量的范围。是机器学习中分析泛化误差的基础。

4. 伯恩斯坦不等式

• 陈述：设 $X_1, \dots, X_n$ 是独立的零均值随机变量，且 $

  X_i

  \le M$ 几乎必然成立。令 $\sigma^2 = \frac{1}{n}\sum_{i=1}^n \text{Var}(X_i)$。则对任意 $t > 0$：

  \[P\left( \frac{1}{n}\sum_{i=1}^n X_i \ge t \right) \le \exp\left( -\frac{n t^2 / 2}{\sigma^2 + M t / 3} \right)\]

• 证明思路： 与霍夫丁类似，使用切尔诺夫界限。关键在于它找到了一个比霍夫丁引理更精细的矩母函数上界，这个上界同时包含了方差 $\sigma^2$ 和范围 $M$ 的信息。

  \[\mathbb{E}[e^{\lambda X}] \le \exp\left( \frac{\sigma^2 \lambda^2 / 2}{1 - M\lambda / 3} \right) \quad \text{(对于 } 0 < \lambda < 3/M \text{)}\]
• 意义：混合型界限。当 $t$ 很小（偏差小）时，行为类似 $\exp(-n t^2 / \sigma^2)$（像基于方差的界）；当 $t$ 很大时，行为类似 $\exp(-n t / M)$（像霍夫丁界）。比霍夫丁更实用，因为它考虑了方差。

---

类别三：基于矩母函数的不等式

这是推导指数浓度不等式的通用框架。

5. 切尔诺夫界限

• 陈述：对于任意随机变量 $X$ 和任意 $t \in \mathbb{R}, \lambda > 0$：

  \[P(X \ge t) \le e^{-\lambda t} \mathbb{E}[e^{\lambda X}]\]

  进而有：

  \[P(X \ge t) \le \inf_{\lambda > 0} e^{-\lambda t} \mathbb{E}[e^{\lambda X}]\]
• 证明思路： 对指示函数 $\mathbb{I}{X \ge t}$，注意到对于 $\lambda > 0$，有 $\mathbb{I}{X \ge t} \le e^{\lambda (X - t)}$。 两边取期望即得证。
• 意义：这是证明指数浓度不等式的”引擎”。霍夫丁、伯恩斯坦等都是通过寻找 $\mathbb{E}[e^{\lambda X}]$ 的上界，然后代入切尔诺夫界限并优化 $\lambda$ 而得。

---

类别四：函数不等式

这类不等式描述了随机变量经过函数变换后的行为。

6. 詹森不等式

• 陈述：如果 $f$ 是一个凸函数，$X$ 是一个随机变量，那么：

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

  如果 $f$ 是凹函数，则不等式方向反转。

• 证明思路（离散情况）： 使用数学归纳法。基础情况 $n=2$ 由凸函数定义直接得出。然后推广到任意 $n$ 和连续情况。
• 意义：解释了为什么方差非负（取 $f(x)=x^2$），以及为什么KL散度非负。是信息论和统计学中的基础。

---

类别五：高级与推广型不等式

7. McDiarmid不等式（有界差不等式）

• 陈述：设 $X_1, \dots, X_n$ 是独立随机变量。设函数 $f$ 满足有界差性质：

  \[|f(x_1, \dots, x_i, \dots, x_n) - f(x_1, \dots, x_i', \dots, x_n)| \le c_i\]

  则对任意 $t > 0$：

  \[P(f(X_1, \dots, X_n) - \mathbb{E}[f(X_1, \dots, X_n)] \ge t) \le \exp\left( -\frac{2t^2}{\sum_{i=1}^n c_i^2} \right)\]
• 证明思路： 构造一个鞅差序列，然后应用Azuma-Hoeffding不等式（霍夫丁在鞅上的推广）。
• 意义：霍夫丁不等式的强力推广。允许变量之间通过函数 $f$ 产生复杂的依赖关系，只要函数值对每个输入的变化不敏感。是分析随机算法和机器学习模型泛化能力的终极工具之一。

---

总结表

不等式	所需条件	界限衰减速度	核心思想证明
马尔可夫	$X \ge 0$	$O(1/t)$	用 $X$ 控制指示函数 $t\mathbb{I}_{X\ge t}$
切比雪夫	有限方差	$O(1/t^2)$	对 $(X-\mathbb{E}X)^2$ 用马尔可夫不等式
霍夫丁	独立、有界	$\exp(-C t^2 / n)$	切尔诺夫界限 + 霍夫丁引理（控制矩母函数）
伯恩斯坦	独立、有界、已知方差	$\exp(-\frac{n t^2}{\sigma^2 + M t})$	切尔诺夫界限 + 更精细的矩母函数上界（含方差）
切尔诺夫	矩母函数存在	$\inf_\lambda e^{-\lambda t} M(\lambda)$	$\mathbb{I}_{X\ge t} \le e^{\lambda(X-t)}$
詹森	凸函数/凹函数	-	凸函数定义 + 归纳法
McDiarmid	有界差性质	$\exp(-C t^2 / \sum c_i^2)$	构造鞅 + Azuma-Hoeffding不等式

学习路径建议：理解这些不等式的最佳方式是掌握它们之间的依赖关系： 马尔可夫 → 切比雪夫 切尔诺夫 → (霍夫丁引理) → 霍夫丁 切尔诺夫 → (更精细引理) → 伯恩斯坦 霍夫丁 → (鞅推广) → Azuma → McDiarmid

---

一、概率不等式

这类不等式主要用于限定随机变量偏离其中心（如期望）的概率。

1. 马尔可夫不等式

• 表述：设 $X$ 是一个非负随机变量，且 $E

  X

  < \infty$，则对任意 $\epsilon > 0$，

  \[P(X \ge \epsilon) \le \frac{E(X)}{\epsilon}\]
• 直观意义：对于一个非负随机变量，其取值大于一个大数的概率，被其期望所控制。期望越小，取大值的概率就越低。
• 计量应用：是证明其他更强大不等式（如切比雪夫不等式）的基础。直接应用较少，但它是概率论的基础构件。

2. 切比雪夫不等式

• 表述：设 $X$ 是一个随机变量，且 $Var(X) < \infty$，则对任意 $\epsilon > 0$，

  \[P(|X - E(X)| \ge \epsilon) \le \frac{Var(X)}{\epsilon^2}\]
• 直观意义：随机变量偏离其期望超过一定范围的概率，被其方差所控制。方差越小，变量就越集中在期望附近。
• 计量应用：
  • 证明一致性：证明估计量的均方收敛。如果 $\hat{\theta}_n$ 是一个估计量，且 $E(\hat{\theta}_n) \to \theta$ (渐近无偏) 且 $Var(\hat{\theta}_n) \to 0$，那么由切比雪夫不等式可直接推出 $\hat{\theta}_n \xrightarrow{P} \theta$ (依概率收敛)。
  • 给出置信区间的保守界限。

3. 切尔诺夫不等式

• 表述：设 $X$ 是一个随机变量，其矩生成函数 $M(t) = E(e^{tX})$ 存在。则对任意 $\epsilon > 0$，

  \[P(X \ge \epsilon) \le \inf_{t > 0} e^{-t\epsilon} M(t)\] \[P(X \le \epsilon) \le \inf_{t < 0} e^{-t\epsilon} M(t)\]
• 直观意义：利用矩生成函数（MGF）给出了比马尔科夫/切比雪夫更紧的尾部概率上界。通过优化参数 $t$，可以得到非常精确的指数型衰减上界。
• 计量应用：
  • 在大偏差理论中非常重要。
  • 用于分析假设检验中两类错误的衰减速率。
  • 在机器学习中，用于推导泛化误差界。

4. 霍夫丁不等式

• 表述：设 $X_1, X_2, \dots, X_n$ 是独立的随机变量，且 $X_i \in [a_i, b_i]$。令 $S_n = \sum_{i=1}^n (X_i - E(X_i))$，则对任意 $\epsilon > 0$，

  \[P(S_n \ge \epsilon) \le \exp\left( \frac{-2\epsilon^2}{\sum_{i=1}^n (b_i - a_i)^2} \right)\]
• 直观意义：对于有界独立随机变量之和，其偏离期望的概率上界以一个指数函数的形式衰减。这比切比雪夫不等式给出的 $1/\epsilon^2$ 衰减要强得多。
• 计量应用：
  • 是统计学习理论的基础，用于证明一致收敛性，从而推导出经验风险最小化（ERM）原则的泛化能力。
  • 在计量中，当误差项有界时，可用于证明估计量的强一致性。

---

二、矩不等式

这类不等式用于关联不同阶的矩，或者限定矩的大小。

1. 柯西-施瓦茨不等式

• 表述：

  • 期望形式：$

    E(XY)

    \le \sqrt{E(X^2)} \sqrt{E(Y^2)}$。等号成立当且仅当 $X$ 和 $Y$ 线性相关。

  • 内积形式：$

    \langle x, y \rangle

    \le |x| \cdot |y|$。

• 直观意义：两个随机变量“协同变化”的程度（协方差的绝对值）被它们各自标准差的上界所控制。
• 计量应用：
  • 证明高斯-马尔可夫定理：在证明OLS估计量是最佳线性无偏估计量（BLUE）时，用于比较不同线性估计量的方差。
  • 在推导估计量的均方误差上界时无处不在。

  • 证明其他不等式（如相关系数 $

    \rho

    \le 1$）。

2. 詹森不等式

• 表述：如果 $g(\cdot)$ 是一个凸函数，那么

  \[g(E(X)) \le E(g(X))\]

  如果 $g(\cdot)$ 是凹函数，则不等式方向相反。

• 直观意义：凸函数的函数值期望，不小于期望的函数值。例如，$[E(X)]^2 \le E(X^2)$。
• 计量应用：
  • 信息论：证明KL散度非负。
  • 说明在风险厌恶下，确定性等价财富小于风险性财富的期望值。
  • 在证明某些估计量的有偏性时有用。

3. 利雅普诺夫不等式

• 表述：设 $0 < s < t$，则

  \[(E|X|^s)^{1/s} \le (E|X|^t)^{1/t}\]
• 直观意义：高阶矩控制了低阶矩。如果一个随机变量的 $t$ 阶矩存在，那么它的所有更低阶矩也都存在。
• 计量应用：在技术性证明中，为了简化问题，常常用高阶矩（如四阶矩）去控制低阶矩（如二阶矩）。

4. 三角不等式

• 表述：对于任意两个向量（或随机变量）$X$ 和 $Y$，有 $|X + Y| \le |X| + |Y|$。
• 直观意义：两边之和大于第三边。
• 计量应用：在几乎所有涉及范数（如证明收敛性）的证明中都会用到，用于将复杂对象分解为更简单的部分并分别控制。

---

总结与使用策略

不等式名称	主要特点	典型应用场景
马尔可夫	最基础，要求非负，界较松	理论基石，证明其他不等式
切比雪夫	利用方差，界为 $O(1/\epsilon^2)$	证明均方收敛，弱大数定律
霍夫丁	针对有界变量和，指数衰减界 $O(e^{-c\epsilon^2})$	统计学习理论，强一致性证明
切尔诺夫	利用MGF，可得到最紧的指数界	大偏差理论，假设检验
柯西-施瓦茨	关联二阶矩，控制协方差	证明BLUE，比较方差，无处不在
詹森	凸函数性质，关联函数期望与期望函数	信息论，经济学中的风险理论
利雅普诺夫	关联不同阶矩	技术性证明，确保低阶矩存在
三角不等式	分解问题，控制各部分	所有涉及范数和度量的证明

在证明中的一般策略：

1. 识别目标：你要证明的是什么？是 $P(\vert \hat{\theta}_n - \theta \vert > \epsilon) \to 0$（一致性）？还是 $E\vert \hat{\theta}_n - \theta \vert^2 \to 0$（均方误差）？
2. 分析对象性质：你的随机变量（或估计量）有什么性质？是有界的吗？（考虑霍夫丁）它的方差容易计算吗？（考虑切比雪夫）它是一个和的形式吗？（考虑霍夫丁、切尔诺夫）它是否满足某种依赖结构（如独立性、鞅）？
3. 选择并应用不等式：根据以上分析，选择最合适的不等式。通常，能利用越强的假设（如有界性、独立性），就能得到越强的结论（如指数收敛）。
4. 组合使用：复杂的证明通常需要组合多个不等式。例如，先用三角不等式分解，再用柯西-施瓦茨不等式控制交叉项，最后对主要项用切比雪夫或霍夫丁不等式。