随机变量的变换的Hoeffding不等式
字数 2973 2025-12-12 07:38:07

随机变量的变换的Hoeffding不等式

我们来循序渐进地理解这个概念，每一步尽量细致准确。

第一步：从背景和问题出发
在概率统计中，我们经常关心随机变量的和与其期望的偏差。
比如，设 \(X_1, X_2, \dots, X_n\) 是独立的随机变量，考虑它们的和

\[S_n = \sum_{i=1}^n X_i \]

我们想知道 \(S_n\) 偏离它的期望 \(\mathbb{E}[S_n]\) 的概率有多大。
切尔诺夫不等式（Chernoff bound）利用矩生成函数给出一个指数型尾概率界，但需要知道矩生成函数的具体形式。Hoeffding 不等式（1963年由 Wassily Hoeffding 提出）给出了在有界随机变量情况下的一个简洁且广泛使用的指数型尾概率不等式，不依赖具体分布，只依赖取值区间。

第二步：基本设定与假设
假设每个 \(X_i\) 是独立随机变量，且 \(a_i \le X_i \le b_i\) 几乎必然成立，其中 \(a_i, b_i\) 是常数。
记区间长度 \(L_i = b_i - a_i\)。
Hoeffding 不等式的关键是利用有界性，得到矩生成函数的一个上界（通过 Hoeffding 引理，我们稍后解释）。

第三步：Hoeffding 引理
先看一个随机变量的情况。设 \(X\) 满足 \(a \le X \le b\) 且 \(\mathbb{E}[X]=0\)。
Hoeffding 引理说：对任意 \(t \in \mathbb{R}\)，

\[\mathbb{E}[e^{tX}] \le \exp\left( \frac{t^2 (b-a)^2}{8} \right)。 \]

证明思路：利用 \(X\) 是 \(a\) 和 \(b\) 两点随机变量的凸组合，再由函数 \(e^{tx}\) 的凸性得到上界，然后对 \(t\) 做优化得到 \((b-a)^2/8\) 这个因子。这个引理说明有界零均值随机变量的矩生成函数被高斯随机变量的矩生成函数（方差为 \((b-a)^2/4\) 的 1/2）所控制。

第四步：推导和的尾概率界
对 \(S_n - \mathbb{E}[S_n] = \sum_{i=1}^n (X_i - \mathbb{E}[X_i])\)，每个 \(Y_i = X_i - \mathbb{E}[X_i]\) 满足 \(a_i - \mathbb{E}[X_i] \le Y_i \le b_i - \mathbb{E}[X_i]\)，区间长度仍然是 \(b_i - a_i\)，且 \(\mathbb{E}[Y_i]=0\)。
对任意 \(t>0\)，用 Markov 不等式：

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

由独立性，

\[\mathbb{E}\left[ e^{\lambda (S_n - \mathbb{E}[S_n])} \right] = \prod_{i=1}^n \mathbb{E}\left[ e^{\lambda Y_i} \right]。 \]

用 Hoeffding 引理，每个因子不超过 \(\exp\left( \frac{\lambda^2 (b_i-a_i)^2}{8} \right)\)。
因此

\[P(S_n - \mathbb{E}[S_n] \ge t) \le \exp\left( -\lambda t + \frac{\lambda^2 \sum_{i=1}^n (b_i-a_i)^2}{8} \right)。 \]

第五步：优化参数 λ
右边是 \(\lambda\) 的二次函数，最小值在 \(\lambda^* = \frac{4t}{\sum_{i=1}^n (b_i-a_i)^2}\) 处取得，代入得到：

\[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)。 \]

由对称性，类似有

\[P(S_n - \mathbb{E}[S_n] \le -t) \le \exp\left( - \frac{2t^2}{\sum_{i=1}^n (b_i-a_i)^2} \right)。 \]

合并得：

\[P\left( |S_n - \mathbb{E}[S_n]| \ge t \right) \le 2\exp\left( - \frac{2t^2}{\sum_{i=1}^n (b_i-a_i)^2} \right)。 \]

这就是 Hoeffding 不等式的标准形式。

第六步：常见特例
如果 \(X_i \in [0,1]\)，则 \(b_i-a_i=1\)，于是

\[P\left( |\bar{X} - \mathbb{E}[\bar{X}]| \ge \epsilon \right) \le 2 e^{-2n\epsilon^2}, \]

其中 \(\bar{X} = S_n/n\)，这里代入了 \(t = n\epsilon\)。
这个形式在机器学习中分析经验风险与期望风险的偏差时非常常用。

第七步：与其它不等式的关系

  • 比切比雪夫不等式（尾部衰减为 \(O(1/t^2)\)）更强，因为 Hoeffding 是指数衰减。
  • 比切尔诺夫界更普适（切尔诺夫界需要知道矩生成函数的具体形式，Hoeffding 只依赖区间）。
  • 伯恩斯坦（Bernstein）不等式进一步引入了方差信息，在有界且方差较小时比 Hoeffding 更紧。

第八步：应用例子

  1. 置信区间：对二项分布参数 \(p\) 的估计，用霍夫丁不等式可以直接给出以概率至少 \(1-\delta\) 有

\[ |\hat{p} - p| \le \sqrt{\frac{\ln(2/\delta)}{2n}}。 \]

  1. 机器学习中的泛化误差界：在有限假设空间的情况下，利用联合界与霍夫丁不等式可推导一致收敛速率。
  2. 随机算法分析：如随机舍入、随机算法的性能集中性分析。

总结
Hoeffding 不等式给出了独立有界随机变量和偏离期望的概率的一个不依赖具体分布、只依赖取值范围的指数型上界，推导基于 Hoeffding 引理 + Markov 不等式 + 独立性，是集中不等式（concentration inequalities）中最基本且重要的工具之一。

随机变量的变换的Hoeffding不等式 我们来循序渐进地理解这个概念，每一步尽量细致准确。 第一步：从背景和问题出发 在概率统计中，我们经常关心随机变量的和与其期望的偏差。 比如，设 \(X_ 1, X_ 2, \dots, X_ n\) 是独立的随机变量，考虑它们的和 \[ S_ n = \sum_ {i=1}^n X_ i \] 我们想知道 \(S_ n\) 偏离它的期望 \(\mathbb{E}[ S_ n ]\) 的概率有多大。 切尔诺夫不等式（Chernoff bound）利用矩生成函数给出一个指数型尾概率界，但需要知道矩生成函数的具体形式。Hoeffding 不等式（1963年由 Wassily Hoeffding 提出）给出了在 有界随机变量 情况下的一个简洁且广泛使用的指数型尾概率不等式，不依赖具体分布，只依赖取值区间。 第二步：基本设定与假设 假设每个 \(X_ i\) 是独立随机变量，且 \(a_ i \le X_ i \le b_ i\) 几乎必然成立，其中 \(a_ i, b_ i\) 是常数。 记区间长度 \(L_ i = b_ i - a_ i\)。 Hoeffding 不等式的关键是利用有界性，得到矩生成函数的一个上界（通过 Hoeffding 引理，我们稍后解释）。 第三步：Hoeffding 引理 先看一个随机变量的情况。设 \(X\) 满足 \(a \le X \le b\) 且 \(\mathbb{E}[ X ]=0\)。 Hoeffding 引理说：对任意 \(t \in \mathbb{R}\)， \[ \mathbb{E}[ e^{tX} ] \le \exp\left( \frac{t^2 (b-a)^2}{8} \right)。 \] 证明思路 ：利用 \(X\) 是 \(a\) 和 \(b\) 两点随机变量的凸组合，再由函数 \(e^{tx}\) 的凸性得到上界，然后对 \(t\) 做优化得到 \((b-a)^2/8\) 这个因子。这个引理说明有界零均值随机变量的矩生成函数被高斯随机变量的矩生成函数（方差为 \((b-a)^2/4\) 的 1/2）所控制。 第四步：推导和的尾概率界 对 \(S_ n - \mathbb{E}[ S_ n] = \sum_ {i=1}^n (X_ i - \mathbb{E}[ X_ i])\)，每个 \(Y_ i = X_ i - \mathbb{E}[ X_ i]\) 满足 \(a_ i - \mathbb{E}[ X_ i] \le Y_ i \le b_ i - \mathbb{E}[ X_ i]\)，区间长度仍然是 \(b_ i - a_ i\)，且 \(\mathbb{E}[ Y_ i ]=0\)。 对任意 \(t>0\)，用 Markov 不等式： \[ P(S_ n - \mathbb{E}[ S_ n] \ge t) = P\left( e^{\lambda (S_ n - \mathbb{E}[ S_ n])} \ge e^{\lambda t} \right) \le e^{-\lambda t} \mathbb{E}\left[ e^{\lambda (S_ n - \mathbb{E}[ S_ n])} \right ]。 \] 由独立性， \[ \mathbb{E}\left[ e^{\lambda (S_ n - \mathbb{E}[ S_ n])} \right] = \prod_ {i=1}^n \mathbb{E}\left[ e^{\lambda Y_ i} \right ]。 \] 用 Hoeffding 引理，每个因子不超过 \(\exp\left( \frac{\lambda^2 (b_ i-a_ i)^2}{8} \right)\)。 因此 \[ P(S_ n - \mathbb{E}[ S_ n] \ge t) \le \exp\left( -\lambda t + \frac{\lambda^2 \sum_ {i=1}^n (b_ i-a_ i)^2}{8} \right)。 \] 第五步：优化参数 λ 右边是 \(\lambda\) 的二次函数，最小值在 \(\lambda^* = \frac{4t}{\sum_ {i=1}^n (b_ i-a_ i)^2}\) 处取得，代入得到： \[ 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)。 \] 由对称性，类似有 \[ P(S_ n - \mathbb{E}[ S_ n] \le -t) \le \exp\left( - \frac{2t^2}{\sum_ {i=1}^n (b_ i-a_ i)^2} \right)。 \] 合并得： \[ P\left( |S_ n - \mathbb{E}[ S_ n]| \ge t \right) \le 2\exp\left( - \frac{2t^2}{\sum_ {i=1}^n (b_ i-a_ i)^2} \right)。 \] 这就是 Hoeffding 不等式 的标准形式。 第六步：常见特例 如果 \(X_ i \in [ 0,1]\)，则 \(b_ i-a_ i=1\)，于是 \[ P\left( |\bar{X} - \mathbb{E}[ \bar{X} ]| \ge \epsilon \right) \le 2 e^{-2n\epsilon^2}, \] 其中 \(\bar{X} = S_ n/n\)，这里代入了 \(t = n\epsilon\)。 这个形式在机器学习中分析经验风险与期望风险的偏差时非常常用。 第七步：与其它不等式的关系 比切比雪夫不等式（尾部衰减为 \(O(1/t^2)\)）更强，因为 Hoeffding 是指数衰减。 比切尔诺夫界更普适（切尔诺夫界需要知道矩生成函数的具体形式，Hoeffding 只依赖区间）。 伯恩斯坦（Bernstein）不等式进一步引入了方差信息，在有界且方差较小时比 Hoeffding 更紧。 第八步：应用例子 置信区间 ：对二项分布参数 \(p\) 的估计，用霍夫丁不等式可以直接给出以概率至少 \(1-\delta\) 有 \[ |\hat{p} - p| \le \sqrt{\frac{\ln(2/\delta)}{2n}}。 \] 机器学习中的泛化误差界 ：在有限假设空间的情况下，利用联合界与霍夫丁不等式可推导一致收敛速率。 随机算法分析 ：如随机舍入、随机算法的性能集中性分析。 总结 Hoeffding 不等式给出了独立有界随机变量和偏离期望的概率的一个 不依赖具体分布、只依赖取值范围 的指数型上界，推导基于 Hoeffding 引理 + Markov 不等式 + 独立性，是集中不等式（concentration inequalities）中最基本且重要的工具之一。