随机变量的变换的Cramér–Chernoff定理（尾部概率的指数型上界）

字数 5272 2025-12-18 22:47:05

随机变量的变换的Cramér–Chernoff定理（尾部概率的指数型上界）

好的，我们现在开始讲解“随机变量的变换的Cramér–Chernoff定理”。这是一个关于随机变量和的尾部概率的、非常重要的指数型上界估计工具，广泛应用于大偏差理论、高维概率、统计学习理论（如泛化误差界）和算法分析（如随机算法的性能保证）中。

第一步：从问题背景和动机开始

我们考虑一个经典问题：设 \(X_1, X_2, \dots, X_n\) 是独立同分布的随机变量，记它们的和为 \(S_n = \sum_{i=1}^n X_i\)。我们想知道 \(S_n\) 偏离其期望值 \(n\mathbb{E}[X]\) 的“尾部概率”，即 \(P(S_n - n\mathbb{E}[X] \ge nt)\) 或 \(P(S_n - n\mathbb{E}[X] \le -nt)\)，其中 \(t > 0\)。

中心极限定理描述了这种偏差在 \(O(\sqrt{n})\) 量级（即 \(t \sim 常数/\sqrt{n}\)）时的渐近正态行为。然而，当偏差是 \(O(n)\) 量级（即固定的 \(t>0\)）时，这种“大偏差”事件的概率会以指数速度衰减，中心极限定理无法给出衰减速率。Cramér–Chernoff定理的目的，就是为这种尾部概率提供一个非渐近的、指数型的上界。这个上界是“最优的”，在最简单的伯努利情形下可以达到。

第二步：核心工具——矩生成函数与累积量生成函数

要得到指数型上界，一个自然的想法是利用指数函数的单调性和马尔可夫不等式。为此，我们引入两个关键函数：

矩生成函数：随机变量 \(X\) 的MGF定义为 \(M_X(\lambda) = \mathbb{E}[e^{\lambda X}]\)，在某个包含0的开区间内有定义。
累积量生成函数：是MGF的对数，\(\psi_X(\lambda) = \log \mathbb{E}[e^{\lambda X}]\)。

对于一个和 \(S_n = \sum_{i=1}^n X_i\)，如果 \(X_i\) 独立，那么 \(M_{S_n}(\lambda) = \prod_{i=1}^n M_{X_i}(\lambda)\)，从而 \(\psi_{S_n}(\lambda) = \sum_{i=1}^n \psi_{X_i}(\lambda)\)。这为处理独立和提供了巨大方便。

第三步：Chernoff界的推导（基本思想）

我们以右尾 \(P(S_n \ge t)\) 为例。对于任意 \(\lambda \ge 0\)，我们有：

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

上述不等式是由马尔可夫不等式（应用于非负随机变量 \(e^{\lambda S_n}\)）直接得到的。

由于 \(X_i\) 独立，\(\mathbb{E}[e^{\lambda S_n}] = \prod_{i=1}^n \mathbb{E}[e^{\lambda X_i}] = \prod_{i=1}^n M_{X_i}(\lambda)\)。于是我们得到：

\[P(S_n \ge t) \le e^{-\lambda t} \prod_{i=1}^n M_{X_i}(\lambda) = \exp\left( -\lambda t + \sum_{i=1}^n \psi_{X_i}(\lambda) \right) \]

这个不等式对所有 \(\lambda \ge 0\) 都成立。为了得到最紧的（即最小的）上界，我们通常在所有可行的 \(\lambda\) 上优化这个界：

\[P(S_n \ge t) \le \inf_{\lambda \ge 0} \exp\left( -\lambda t + \sum_{i=1}^n \psi_{X_i}(\lambda) \right) = \exp\left( - \sup_{\lambda \ge 0} \left[ \lambda t - \sum_{i=1}^n \psi_{X_i}(\lambda) \right] \right) \]

第四步：Cramér变换与大偏差率函数

上一步中出现的优化问题，自然地引出了一个核心函数：

\[I_n(t) = \sup_{\lambda \ge 0} \left[ \lambda t - \sum_{i=1}^n \psi_{X_i}(\lambda) \right] \]

这个函数 \(I_n(t)\) 被称为Cramér变换或速率函数（在 \(t \ge \mathbb{E}[S_n]\) 时的右尾部分）。它衡量了“和为 \(t\) 这个事件”的“稀有程度”，其值越大，对应的概率上界 \(e^{-I_n(t)}\) 就越小。

在独立同分布情形下，\(\psi_{X_i}(\lambda) = \psi_X(\lambda)\) 对每个 \(i\) 都相同，所以：

\[I_n(t) = n \cdot \sup_{\lambda \ge 0} \left[ \lambda (t/n) - \psi_X(\lambda) \right] = n \cdot I_X(t/n) \]

这里， \(I_X(a) = \sup_{\lambda} [\lambda a - \psi_X(\lambda)]\) 是单个随机变量 \(X\) 的大偏差率函数。注意，此时的优化范围可以是 \(\lambda \in \mathbb{R}\)（当考虑左尾时，需要 \(\lambda \le 0\)）。

因此，Cramér–Chernoff定理 的核心结论可以表述为：对于独立同分布随机变量序列，

\[P\left( \frac{1}{n}S_n \ge a \right) \le \exp\left( -n I_X(a) \right), \quad \text{对于所有} a > \mathbb{E}[X] \]

其中 \(I_X(a) = \sup_{\lambda \in \mathbb{R}} [\lambda a - \psi_X(\lambda)]\)。

第五步：定理的精确表述与关键性质

现在，我们可以给出一个更正式的表述：

定理 (Cramér–Chernoff)：
设 \(X_1, \dots, X_n\) 是独立同分布的随机变量，其累积量生成函数 \(\psi_X(\lambda) = \log \mathbb{E}[e^{\lambda X}]\) 在包含0的某个开区间内有定义。定义大偏差率函数 \(I_X(a) = \sup_{\lambda \in \mathbb{R}} \{ \lambda a - \psi_X(\lambda) \}\)。那么，对于任意 \(a > \mathbb{E}[X]\)，有：

\[P\left( \frac{1}{n} \sum_{i=1}^n X_i \ge a \right) \le e^{-n I_X(a)}. \]

类似地，对于任意 \(a < \mathbb{E}[X]\)，有：

\[P\left( \frac{1}{n} \sum_{i=1}^n X_i \le a \right) \le e^{-n I_X(a)}. \]

关键性质：

非负性： \(I_X(a) \ge 0\)。
凸性： \(I_X(a)\) 是凸函数（作为一组仿射函数 \(\lambda a - \psi_X(\lambda)\) 的上确界）。
极小点：在 \(a = \mathbb{E}[X]\) 处， \(I_X(\mathbb{E}[X]) = 0\)。这很直观，因为样本均值接近期望是典型事件，概率很大（不呈指数衰减）。
最优性：在很一般的条件下，Cramér定理（大偏差原理）指出，这个上界是渐近最优的，即 \(\frac{1}{n} \log P\left( \frac{1}{n} S_n \in A \right) \to -\inf_{a \in A} I_X(a)\)。这意味着Chernoff给出的指数衰减速率 \(I_X(a)\) 是无法被进一步实质改进的。

第六步：经典特例——有界随机变量与Hoeffding界

为了具体理解如何应用，考虑一个特例：设 \(X_i \in [0, 1]\) 且 \(\mathbb{E}[X_i] = \mu\)。我们可以推导出著名的Hoeffding界 作为Cramér–Chernoff定理的一个推论。

关键在于估计 \(\psi_X(\lambda)\)。利用 \(e^{\lambda x}\) 的凸性，对于 \(x \in [0,1]\)，有 \(e^{\lambda x} \le 1 - x + x e^{\lambda}\)。取期望，并利用 \(\mathbb{E}[X] = \mu\)，得到：

\[M_X(\lambda) \le 1 - \mu + \mu e^{\lambda} = 1 + \mu(e^{\lambda} - 1) \le \exp(\mu(e^{\lambda} - 1)) \]

但更常用的Hoeffding引理给出：对于任意 \(\lambda\)，有 \(\psi_X(\lambda) \le \frac{\lambda^2}{8}\)（当 \(X \in [a, b]\) 时，上界为 \(\lambda^2(b-a)^2/8\)）。这里我们取 \(a=0, b=1\)。

那么，对于中心化的随机变量 \(Y_i = X_i - \mu\)，有 \(Y_i \in [-\mu, 1-\mu]\)，其范围为1。Hoeffding引理给出 \(\psi_{Y_i}(\lambda) \le \lambda^2/8\)。

现在，应用Cramér–Chernoff思想于 \(S_n - n\mu = \sum Y_i\)：
对于 \(t > 0\)，

\[P(S_n - n\mu \ge nt) \le \inf_{\lambda \ge 0} \exp\left( -\lambda n t + n \cdot \frac{\lambda^2}{8} \right) \]

右边是关于 \(\lambda\) 的二次函数，在 \(\lambda = 4t\) 处取得最小值 \(\exp(-n \cdot 2t^2)\)。所以：

\[P\left( \frac{1}{n}S_n \ge \mu + t \right) \le e^{-2n t^2} \]

这就是Hoeffding不等式。可以看到，它是通过一个更“宽松”但易于计算的 \(\psi_X(\lambda)\) 上界（这里是二次函数），代入Cramér–Chernoff框架得到的。

第七步：总结

总而言之，Cramér–Chernoff定理 提供了一个系统性的、基于矩生成函数的框架，用于推导独立随机变量和（或其均值）的指数型尾部概率上界。其核心步骤是：

利用马尔可夫不等式对指数函数 \(e^{\lambda S_n}\) 放缩。
利用独立性将矩生成函数分解为乘积。
对参数 \(\lambda\) 进行优化，以得到最紧的上界，这个优化问题定义了大偏差率函数 \(I_X(a)\)。
最终的上界形式为 \(e^{-n I_X(a)}\)，它不仅是非渐近有效的，而且给出了正确的指数衰减速率。

这个定理是连接经典概率不等式（如Chernoff界、Hoeffding界、Bernstein界）和大偏差理论的桥梁，是现代概率论、统计学和理论计算机科学中分析尾部概率的基础工具。

随机变量的变换的Cramér–Chernoff定理（尾部概率的指数型上界）好的，我们现在开始讲解“随机变量的变换的Cramér–Chernoff定理”。这是一个关于随机变量和的尾部概率的、非常重要的指数型上界估计工具，广泛应用于大偏差理论、高维概率、统计学习理论（如泛化误差界）和算法分析（如随机算法的性能保证）中。第一步：从问题背景和动机开始我们考虑一个经典问题：设 \( X_ 1, X_ 2, \dots, X_ n \) 是独立同分布的随机变量，记它们的和为 \( S_ n = \sum_ {i=1}^n X_ i \)。我们想知道 \( S_ n \) 偏离其期望值 \( n\mathbb{E}[ X] \) 的“尾部概率”，即 \( P(S_ n - n\mathbb{E}[ X] \ge nt) \) 或 \( P(S_ n - n\mathbb{E}[ X ] \le -nt) \)，其中 \( t > 0 \)。中心极限定理描述了这种偏差在 \( O(\sqrt{n}) \) 量级（即 \( t \sim 常数/\sqrt{n} \)）时的渐近正态行为。然而，当偏差是 \( O(n) \) 量级（即固定的 \( t>0 \)）时，这种“大偏差”事件的概率会以指数速度衰减，中心极限定理无法给出衰减速率。Cramér–Chernoff定理的目的，就是为这种尾部概率提供一个非渐近的、指数型的上界。这个上界是“最优的”，在最简单的伯努利情形下可以达到。第二步：核心工具——矩生成函数与累积量生成函数要得到指数型上界，一个自然的想法是利用指数函数的单调性和马尔可夫不等式。为此，我们引入两个关键函数：矩生成函数：随机变量 \( X \) 的MGF定义为 \( M_ X(\lambda) = \mathbb{E}[ e^{\lambda X} ] \)，在某个包含0的开区间内有定义。累积量生成函数：是MGF的对数，\( \psi_ X(\lambda) = \log \mathbb{E}[ e^{\lambda X} ] \)。对于一个和 \( S_ n = \sum_ {i=1}^n X_ i \)，如果 \( X_ i \) 独立，那么 \( M_ {S_ n}(\lambda) = \prod_ {i=1}^n M_ {X_ i}(\lambda) \)，从而 \( \psi_ {S_ n}(\lambda) = \sum_ {i=1}^n \psi_ {X_ i}(\lambda) \)。这为处理独立和提供了巨大方便。第三步：Chernoff界的推导（基本思想）我们以右尾 \( P(S_ n \ge t) \) 为例。对于任意 \( \lambda \ge 0 \)，我们有： \[ P(S_ n \ge t) = P(e^{\lambda S_ n} \ge e^{\lambda t}) \le e^{-\lambda t} \mathbb{E}[ e^{\lambda S_ n} ] \] 上述不等式是由马尔可夫不等式（应用于非负随机变量 \( e^{\lambda S_ n} \)）直接得到的。由于 \( X_ i \) 独立，\( \mathbb{E}[ e^{\lambda S_ n}] = \prod_ {i=1}^n \mathbb{E}[ e^{\lambda X_ i}] = \prod_ {i=1}^n M_ {X_ i}(\lambda) \)。于是我们得到： \[ P(S_ n \ge t) \le e^{-\lambda t} \prod_ {i=1}^n M_ {X_ i}(\lambda) = \exp\left( -\lambda t + \sum_ {i=1}^n \psi_ {X_ i}(\lambda) \right) \] 这个不等式对所有 \( \lambda \ge 0 \) 都成立。为了得到最紧的（即最小的）上界，我们通常在所有可行的 \( \lambda \) 上优化这个界： \[ P(S_ n \ge t) \le \inf_ {\lambda \ge 0} \exp\left( -\lambda t + \sum_ {i=1}^n \psi_ {X_ i}(\lambda) \right) = \exp\left( - \sup_ {\lambda \ge 0} \left[ \lambda t - \sum_ {i=1}^n \psi_ {X_ i}(\lambda) \right ] \right) \] 第四步：Cramér变换与大偏差率函数上一步中出现的优化问题，自然地引出了一个核心函数： \[ I_ n(t) = \sup_ {\lambda \ge 0} \left[ \lambda t - \sum_ {i=1}^n \psi_ {X_ i}(\lambda) \right ] \] 这个函数 \( I_ n(t) \) 被称为 Cramér变换或速率函数（在 \( t \ge \mathbb{E}[ S_ n] \) 时的右尾部分）。它衡量了“和为 \( t \) 这个事件”的“稀有程度”，其值越大，对应的概率上界 \( e^{-I_ n(t)} \) 就越小。在独立同分布情形下，\( \psi_ {X_ i}(\lambda) = \psi_ X(\lambda) \) 对每个 \( i \) 都相同，所以： \[ I_ n(t) = n \cdot \sup_ {\lambda \ge 0} \left[ \lambda (t/n) - \psi_ X(\lambda) \right] = n \cdot I_ X(t/n) \] 这里， \( I_ X(a) = \sup_ {\lambda} [ \lambda a - \psi_ X(\lambda)] \) 是单个随机变量 \( X \) 的大偏差率函数。注意，此时的优化范围可以是 \( \lambda \in \mathbb{R} \)（当考虑左尾时，需要 \( \lambda \le 0 \)）。因此， Cramér–Chernoff定理的核心结论可以表述为：对于独立同分布随机变量序列， \[ P\left( \frac{1}{n}S_ n \ge a \right) \le \exp\left( -n I_ X(a) \right), \quad \text{对于所有} a > \mathbb{E}[ X ] \] 其中 \( I_ X(a) = \sup_ {\lambda \in \mathbb{R}} [ \lambda a - \psi_ X(\lambda) ] \)。第五步：定理的精确表述与关键性质现在，我们可以给出一个更正式的表述：定理 (Cramér–Chernoff) ：设 \( X_ 1, \dots, X_ n \) 是独立同分布的随机变量，其累积量生成函数 \( \psi_ X(\lambda) = \log \mathbb{E}[ e^{\lambda X}] \) 在包含0的某个开区间内有定义。定义大偏差率函数 \( I_ X(a) = \sup_ {\lambda \in \mathbb{R}} \{ \lambda a - \psi_ X(\lambda) \} \)。那么，对于任意 \( a > \mathbb{E}[ X ] \)，有： \[ P\left( \frac{1}{n} \sum_ {i=1}^n X_ i \ge a \right) \le e^{-n I_ X(a)}. \] 类似地，对于任意 \( a < \mathbb{E}[ X ] \)，有： \[ P\left( \frac{1}{n} \sum_ {i=1}^n X_ i \le a \right) \le e^{-n I_ X(a)}. \] 关键性质：非负性： \( I_ X(a) \ge 0 \)。凸性： \( I_ X(a) \) 是凸函数（作为一组仿射函数 \( \lambda a - \psi_ X(\lambda) \) 的上确界）。极小点：在 \( a = \mathbb{E}[ X] \) 处， \( I_ X(\mathbb{E}[ X ]) = 0 \)。这很直观，因为样本均值接近期望是典型事件，概率很大（不呈指数衰减）。最优性：在很一般的条件下，Cramér定理（大偏差原理）指出，这个上界是渐近最优的，即 \( \frac{1}{n} \log P\left( \frac{1}{n} S_ n \in A \right) \to -\inf_ {a \in A} I_ X(a) \)。这意味着Chernoff给出的指数衰减速率 \( I_ X(a) \) 是无法被进一步实质改进的。第六步：经典特例——有界随机变量与Hoeffding界为了具体理解如何应用，考虑一个特例：设 \( X_ i \in [ 0, 1] \) 且 \( \mathbb{E}[ X_ i] = \mu \)。我们可以推导出著名的 Hoeffding界作为Cramér–Chernoff定理的一个推论。关键在于估计 \( \psi_ X(\lambda) \)。利用 \( e^{\lambda x} \) 的凸性，对于 \( x \in [ 0,1] \)，有 \( e^{\lambda x} \le 1 - x + x e^{\lambda} \)。取期望，并利用 \( \mathbb{E}[ X ] = \mu \)，得到： \[ M_ X(\lambda) \le 1 - \mu + \mu e^{\lambda} = 1 + \mu(e^{\lambda} - 1) \le \exp(\mu(e^{\lambda} - 1)) \] 但更常用的Hoeffding引理给出：对于任意 \( \lambda \)，有 \( \psi_ X(\lambda) \le \frac{\lambda^2}{8} \)（当 \( X \in [ a, b ] \) 时，上界为 \( \lambda^2(b-a)^2/8 \)）。这里我们取 \( a=0, b=1 \)。那么，对于中心化的随机变量 \( Y_ i = X_ i - \mu \)，有 \( Y_ i \in [ -\mu, 1-\mu] \)，其范围为1。Hoeffding引理给出 \( \psi_ {Y_ i}(\lambda) \le \lambda^2/8 \)。现在，应用Cramér–Chernoff思想于 \( S_ n - n\mu = \sum Y_ i \)：对于 \( t > 0 \)， \[ P(S_ n - n\mu \ge nt) \le \inf_ {\lambda \ge 0} \exp\left( -\lambda n t + n \cdot \frac{\lambda^2}{8} \right) \] 右边是关于 \( \lambda \) 的二次函数，在 \( \lambda = 4t \) 处取得最小值 \( \exp(-n \cdot 2t^2) \)。所以： \[ P\left( \frac{1}{n}S_ n \ge \mu + t \right) \le e^{-2n t^2} \] 这就是Hoeffding不等式。可以看到，它是通过一个更“宽松”但易于计算的 \( \psi_ X(\lambda) \) 上界（这里是二次函数），代入Cramér–Chernoff框架得到的。第七步：总结总而言之， Cramér–Chernoff定理提供了一个系统性的、基于矩生成函数的框架，用于推导独立随机变量和（或其均值）的指数型尾部概率上界。其核心步骤是：利用马尔可夫不等式对指数函数 \( e^{\lambda S_ n} \) 放缩。利用独立性将矩生成函数分解为乘积。对参数 \( \lambda \) 进行优化，以得到最紧的上界，这个优化问题定义了大偏差率函数 \( I_ X(a) \)。最终的上界形式为 \( e^{-n I_ X(a)} \)，它不仅是非渐近有效的，而且给出了正确的指数衰减速率。这个定理是连接经典概率不等式（如Chernoff界、Hoeffding界、Bernstein界）和大偏差理论的桥梁，是现代概率论、统计学和理论计算机科学中分析尾部概率的基础工具。