随机变量的变换的Hoeffding不等式 Hoeffding不等式是概率论中一个重要的浓度不等式，用于刻画有界随机变量和与其期望之间偏差的概率上界。它特别适用于独立随机变量的和，并在机器学习、统计推断和算法分析中有广泛应用。下面逐步介绍其核心概念。 1. 问题背景：有界随机变量的和 设 \( X_ 1, X_ 2, \dots, X_ n \) 是独立的随机变量，且每个 \( X_ i \) 满足 \( a_ i \leq X_ i \leq b_ i \)。定义部分和 \( S_ n = \sum_ {i=1}^n X_ i \) 及其期望 \( \mathbb{E}[ S_ n] = \sum_ {i=1}^n \mathbb{E}[ X_ i] \)。Hoeffding不等式关注的是偏差 \( |S_ n - \mathbb{E}[ S_ n ]| \) 超过某一阈值 \( t \) 的概率上界。 2. 核心思想：利用矩生成函数控制尾概率 Hoeffding不等式的证明基于以下步骤： 切尔诺夫界（Chernoff Bound） ：对任意 \( \lambda > 0 \)，有 \[ \mathbb{P}(S_ n - \mathbb{E}[ S_ n] \geq t) \leq e^{-\lambda t} \mathbb{E}[ e^{\lambda (S_ n - \mathbb{E}[ S_ n])} ]. \] 独立性分解 ：由于 \( X_ i \) 独立，矩生成函数可分解为 \[ \mathbb{E}[ e^{\lambda (S_ n - \mathbb{E}[ S_ n])}] = \prod_ {i=1}^n \mathbb{E}[ e^{\lambda (X_ i - \mathbb{E}[ X_ i])} ]. \] Hoeffding引理 ：若 \( X \) 满足 \( a \leq X \leq b \)，则对任意 \( \lambda \)，有 \[ \mathbb{E}[ e^{\lambda (X - \mathbb{E}[ X])} ] \leq e^{\lambda^2 (b-a)^2 / 8}. \] 这一关键结论通过凸性优化得到，将随机变量约束在区间内的信息转化为生成函数的指数上界。 3. 不等式的一般形式 结合上述步骤，Hoeffding不等式给出如下上界： \[ \mathbb{P}(S_ n - \mathbb{E}[ S_ n] \geq t) \leq \exp\left( -\frac{2t^2}{\sum_ {i=1}^n (b_ i - a_ i)^2} \right). \] 类似地，对另一侧偏差有 \[ \mathbb{P}(S_ n - \mathbb{E}[ S_ n] \leq -t) \leq \exp\left( -\frac{2t^2}{\sum_ {i=1}^n (b_ i - a_ i)^2} \right). \] 联合两者可得双边不等式： \[ \mathbb{P}(|S_ n - \mathbb{E}[ S_ n]| \geq t) \leq 2\exp\left( -\frac{2t^2}{\sum_ {i=1}^n (b_ i - a_ i)^2} \right). \] 4. 特例：均值估计 若所有 \( X_ i \) 同分布于区间 \([ a, b]\)，则样本均值 \( \bar{X}_ n = S_ n / n \) 满足： \[ \mathbb{P}(|\bar{X}_ n - \mathbb{E}[ \bar{X}_ n ]| \geq \varepsilon) \leq 2\exp\left( -\frac{2n\varepsilon^2}{(b-a)^2} \right). \] 这一形式直接应用于统计估计的误差分析，表明误差以指数速度衰减。 5. 应用与扩展 机器学习 ：用于分析经验风险最小化的一般化误差界。 多臂赌博机问题 ：结合置信上界（UCB）算法进行探索与利用的平衡。 推广性 ：Hoeffding不等式可扩展至亚高斯随机变量、鞅差序列等更一般设定。 Hoeffding不等式的价值在于其简洁性和广泛适用性，为有界随机变量和的尾部概率提供了不依赖于具体分布的显式控制。