随机变量的变换的Cramér–Chernoff定理
字数 3262 2025-12-06 11:27:00

随机变量的变换的Cramér–Chernoff定理

  1. 基本背景与动机
    在概率论与统计学中，评估一个随机变量（或随机变量之和）的尾概率（即取极端值的概率）至关重要。Cramér–Chernoff定理（也称为Chernoff界）提供了一个强大且通用的框架，用于为随机变量的上尾或下尾概率生成指数衰减的紧致上界。它是切尔诺夫界的理论基础和精确化表述。与仅使用二阶矩的切比雪夫不等式相比，它利用了矩生成函数，从而能得出在尾部概率估计上指数级更优的界。

  2. 核心工具：矩生成函数与对数矩生成函数
    设 \(X\) 是一个随机变量。其矩生成函数 定义为 \(M_X(t) = \mathbb{E}[e^{tX}]\)，其中 \(t\) 是实数参数，且在其定义域内取值。其对数矩生成函数 定义为 \(\psi_X(t) = \ln M_X(t) = \ln \mathbb{E}[e^{tX}]\)。这个函数是Cramér–Chernoff定理的核心。它对 \(t\) 是凸函数，并且在 \(t=0\) 时值为0，导数为 \(\mathbb{E}[X]\)（如果存在）。我们需要关注其共轭函数（或Fenchel-Legendre变换）。

  3. 共轭函数（Fenchel-Legendre变换）
    对任意实数 \(a\)，我们定义 \(\psi_X\) 的共轭函数为：

\[ \psi_X^*(a) = \sup_{t \in \mathbb{R}} \{ a t - \psi_X(t) \}. \]

这个函数 \(\psi_X^*\) 是Cramér–Chernoff定理中指数衰减率的具体形式。其几何意义是：在所有过原点的直线 \(t \mapsto a t\) 中，找到与曲线 \(\psi_X(t)\) 在 \(t\) 点处垂直距离最大的点，这个最大距离（的负数）就是 \(\psi_X^*(a)\)。\(\psi_X^*(a)\) 总是非负的凸函数，且当 \(a = \mathbb{E}[X]\) 时达到最小值0。

  1. Cramér–Chernoff定理的表述
    设 \(X\) 是一个随机变量，其对数矩生成函数 \(\psi_X(t)\) 在包含0的某个开区间上有定义。则对于任意阈值 \(a\)，我们有：

\[ \mathbb{P}(X \ge a) \le \exp\left( -\psi_X^*(a) \right), \quad \text{对所有 } a \ge \mathbb{E}[X] \text{ 成立}. \]

类似地，对于下尾：

\[ \mathbb{P}(X \le a) \le \exp\left( -\psi_X^*(a) \right), \quad \text{对所有 } a \le \mathbb{E}[X] \text{ 成立}. \]

这个上界被称为Chernoff上界。定理的关键在于，它明确给出了尾概率衰减的速率函数 \(\psi_X^*(a)\)，并且这个界是“紧的”或“渐近精确的”，在某种意义下，当 \(a\) 远离均值时，这个指数衰减率是最优的。

  1. 定理的证明思路
    证明基于一个简单的“指数放大”技巧和马尔可夫不等式。
  • 第一步（指数控制）： 对任意 \(t > 0\)，有 \(\mathbb{P}(X \ge a) = \mathbb{P}(e^{tX} \ge e^{ta})\)。因为指数函数是单调递增的。
  • 第二步（马尔可夫不等式）： 应用马尔可夫不等式，\(\mathbb{P}(e^{tX} \ge e^{ta}) \le e^{-ta} \mathbb{E}[e^{tX}] = e^{-ta} M_X(t) = e^{-(ta - \psi_X(t))}\)。
  • 第三步（优化参数）： 这个上界对任意 \(t > 0\) 都成立。为了得到最紧的界，我们选择最小化右边指数的 \(t\) 值：

\[ \mathbb{P}(X \ge a) \le \inf_{t > 0} e^{-(ta - \psi_X(t))} = \exp\left( -\sup_{t > 0} \{ ta - \psi_X(t) \} \right). \]

  • 第四步（扩展到共轭函数）： 由于 \(\psi_X^*(a)\) 的定义是取所有实数 \(t\) 的上确界，而当我们考虑上尾 (\(a \ge \mathbb{E}[X]\)) 时，上确界在 \(t > 0\) 处达到（因为此时导数在0点为正，函数在正方向增长）。因此，\(\sup_{t > 0} \{ ta - \psi_X(t) \} = \psi_X^*(a)\)。最终得到 \(\mathbb{P}(X \ge a) \le \exp(-\psi_X^*(a))\)。下尾的证明类似，取 \(t < 0\)。
  1. 应用于独立同分布和：经典Chernoff界
    最重要的应用场景是独立同分布随机变量和。设 \(S_n = X_1 + ... + X_n\)，其中 \(X_i\) 独立同分布。其对数矩生成函数具有可加性：\(\psi_{S_n}(t) = n \psi_X(t)\)。那么 \(S_n\) 的共轭函数为 \(\psi_{S_n}^*(a) = n \psi_X^*(a/n)\)。应用定理得：

\[ \mathbb{P}\left( \frac{S_n}{n} \ge a \right) \le \exp\left( -n \psi_X^*(a) \right) \quad (a \ge \mathbb{E}[X]). \]

这个形式更为常见。指数衰减率 \(n \psi_X^*(a)\) 是线性的，意味着样本均值偏离其期望的概率随着 \(n\) 增大而指数衰减。通过计算具体分布（如伯努利分布、正态分布、泊松分布）的 \(\psi_X^*(a)\)，可以得到著名的Chernoff-Hoeffding界、次高斯尾界等具体形式。

  1. 定理的深层意义与扩展
  • 大偏差理论： Cramér定理是Cramér–Chernoff定理的直接推广，描述了独立同分布随机变量和以指数速率偏离其均值的精确渐近概率，即 \(\mathbb{P}(S_n/n \in A) \approx e^{-n I(A)}\)，其中 \(I(A) = \inf_{a \in A} \psi_X^*(a)\)。这里 \(\psi_X^*\) 被称为速率函数，是随机过程大偏差原理的核心。
  • 最优性： 在独立同分布和的情况下，由Cramér定理可知，Chernoff上界给出的衰减指数 \(n\psi_X^*(a)\) 是精确的，即 \(\lim_{n\to\infty} \frac{1}{n} \ln \mathbb{P}(S_n/n \ge a) = -\psi_X^*(a)\)。这证明了该界的渐近紧致性。
  • 与中心极限定理的关系： 中心极限定理描述的是“典型波动”（\(O(1/\sqrt{n})\) 尺度）的分布，尾部是多项式衰减。Cramér–Chernoff定理描述的是“大偏差”（\(O(1)\) 尺度）的概率，尾部是指数衰减。二者刻画了随机变量和在不同尺度下的行为。

总而言之，Cramér–Chernoff定理通过矩生成函数和对数矩生成函数的共轭函数，为随机变量尾概率提供了一个理论上紧致、计算上可行、应用广泛的指数型上界，是连接概率不等式、浓度不等式和大偏差理论的基石。

随机变量的变换的Cramér–Chernoff定理 基本背景与动机 在概率论与统计学中，评估一个随机变量（或随机变量之和）的尾概率（即取极端值的概率）至关重要。Cramér–Chernoff定理（也称为Chernoff界）提供了一个强大且通用的框架，用于为随机变量的上尾或下尾概率生成指数衰减的紧致上界。它是切尔诺夫界的理论基础和精确化表述。与仅使用二阶矩的切比雪夫不等式相比，它利用了矩生成函数，从而能得出在尾部概率估计上指数级更优的界。 核心工具：矩生成函数与对数矩生成函数 设 \( X \) 是一个随机变量。其 矩生成函数 定义为 \( M_ X(t) = \mathbb{E}[ e^{tX}] \)，其中 \( t \) 是实数参数，且在其定义域内取值。其 对数矩生成函数 定义为 \( \psi_ X(t) = \ln M_ X(t) = \ln \mathbb{E}[ e^{tX}] \)。这个函数是Cramér–Chernoff定理的核心。它对 \( t \) 是凸函数，并且在 \( t=0 \) 时值为0，导数为 \( \mathbb{E}[ X] \)（如果存在）。我们需要关注其 共轭函数 （或Fenchel-Legendre变换）。 共轭函数（Fenchel-Legendre变换） 对任意实数 \( a \)，我们定义 \( \psi_ X \) 的共轭函数为： \[ \psi_ X^ (a) = \sup_ {t \in \mathbb{R}} \{ a t - \psi_ X(t) \}. \] 这个函数 \( \psi_ X^ \) 是Cramér–Chernoff定理中指数衰减率的具体形式。其几何意义是：在所有过原点的直线 \( t \mapsto a t \) 中，找到与曲线 \( \psi_ X(t) \) 在 \( t \) 点处垂直距离最大的点，这个最大距离（的负数）就是 \( \psi_ X^ (a) \)。\( \psi_ X^ (a) \) 总是非负的凸函数，且当 \( a = \mathbb{E}[ X ] \) 时达到最小值0。 Cramér–Chernoff定理的表述 设 \( X \) 是一个随机变量，其对数矩生成函数 \( \psi_ X(t) \) 在包含0的某个开区间上有定义。则对于任意阈值 \( a \)，我们有： \[ \mathbb{P}(X \ge a) \le \exp\left( -\psi_ X^ (a) \right), \quad \text{对所有 } a \ge \mathbb{E}[ X ] \text{ 成立}. \] 类似地，对于下尾： \[ \mathbb{P}(X \le a) \le \exp\left( -\psi_ X^ (a) \right), \quad \text{对所有 } a \le \mathbb{E}[ X ] \text{ 成立}. \] 这个上界被称为 Chernoff上界 。定理的关键在于，它明确给出了尾概率衰减的速率函数 \( \psi_ X^* (a) \)，并且这个界是“紧的”或“渐近精确的”，在某种意义下，当 \( a \) 远离均值时，这个指数衰减率是最优的。 定理的证明思路 证明基于一个简单的“指数放大”技巧和马尔可夫不等式。 第一步（指数控制） ： 对任意 \( t > 0 \)，有 \( \mathbb{P}(X \ge a) = \mathbb{P}(e^{tX} \ge e^{ta}) \)。因为指数函数是单调递增的。 第二步（马尔可夫不等式） ： 应用马尔可夫不等式，\( \mathbb{P}(e^{tX} \ge e^{ta}) \le e^{-ta} \mathbb{E}[ e^{tX}] = e^{-ta} M_ X(t) = e^{-(ta - \psi_ X(t))} \)。 第三步（优化参数） ： 这个上界对任意 \( t > 0 \) 都成立。为了得到最紧的界，我们选择最小化右边指数的 \( t \) 值： \[ \mathbb{P}(X \ge a) \le \inf_ {t > 0} e^{-(ta - \psi_ X(t))} = \exp\left( -\sup_ {t > 0} \{ ta - \psi_ X(t) \} \right). \] 第四步（扩展到共轭函数） ： 由于 \( \psi_ X^ (a) \) 的定义是取所有实数 \( t \) 的上确界，而当我们考虑上尾 (\(a \ge \mathbb{E}[ X]\)) 时，上确界在 \( t > 0 \) 处达到（因为此时导数在0点为正，函数在正方向增长）。因此，\( \sup_ {t > 0} \{ ta - \psi_ X(t) \} = \psi_ X^ (a) \)。最终得到 \( \mathbb{P}(X \ge a) \le \exp(-\psi_ X^* (a)) \)。下尾的证明类似，取 \( t < 0 \)。 应用于独立同分布和：经典Chernoff界 最重要的应用场景是独立同分布随机变量和。设 \( S_ n = X_ 1 + ... + X_ n \)，其中 \( X_ i \) 独立同分布。其对数矩生成函数具有可加性：\( \psi_ {S_ n}(t) = n \psi_ X(t) \)。那么 \( S_ n \) 的共轭函数为 \( \psi_ {S_ n}^ (a) = n \psi_ X^ (a/n) \)。应用定理得： \[ \mathbb{P}\left( \frac{S_ n}{n} \ge a \right) \le \exp\left( -n \psi_ X^ (a) \right) \quad (a \ge \mathbb{E}[ X ]). \] 这个形式更为常见。指数衰减率 \( n \psi_ X^ (a) \) 是线性的，意味着样本均值偏离其期望的概率随着 \( n \) 增大而指数衰减。通过计算具体分布（如伯努利分布、正态分布、泊松分布）的 \( \psi_ X^* (a) \)，可以得到著名的Chernoff-Hoeffding界、次高斯尾界等具体形式。 定理的深层意义与扩展 大偏差理论 ： Cramér定理是Cramér–Chernoff定理的直接推广，描述了独立同分布随机变量和以指数速率偏离其均值的精确渐近概率，即 \( \mathbb{P}(S_ n/n \in A) \approx e^{-n I(A)} \)，其中 \( I(A) = \inf_ {a \in A} \psi_ X^ (a) \)。这里 \( \psi_ X^ \) 被称为 速率函数 ，是随机过程大偏差原理的核心。 最优性 ： 在独立同分布和的情况下，由Cramér定理可知，Chernoff上界给出的衰减指数 \( n\psi_ X^ (a) \) 是精确的，即 \( \lim_ {n\to\infty} \frac{1}{n} \ln \mathbb{P}(S_ n/n \ge a) = -\psi_ X^ (a) \)。这证明了该界的渐近紧致性。 与中心极限定理的关系 ： 中心极限定理描述的是“典型波动”（\( O(1/\sqrt{n}) \) 尺度）的分布，尾部是多项式衰减。Cramér–Chernoff定理描述的是“大偏差”（\( O(1) \) 尺度）的概率，尾部是指数衰减。二者刻画了随机变量和在不同尺度下的行为。 总而言之，Cramér–Chernoff定理通过矩生成函数和对数矩生成函数的共轭函数，为随机变量尾概率提供了一个理论上紧致、计算上可行、应用广泛的指数型上界，是连接概率不等式、浓度不等式和大偏差理论的基石。