随机变量的变换的Hoeffding引理 Hoeffding引理是概率论中的一个重要工具，它为有界随机变量的矩生成函数（MGF）提供了一个尖锐的上界，是推导Hoeffding不等式的基础。下面逐步展开讲解。 1. 问题背景：有界随机变量的矩生成函数 设随机变量 \( X \) 满足 \( \mathbb{E}[ X] = 0 \) 且 \( a \leq X \leq b \)。我们希望控制其矩生成函数 \( M_ X(t) = \mathbb{E}[ e^{tX}] \) 的增长速度。直接计算 \( M_ X(t) \) 通常困难，但Hoeffding引理给出了一个简洁的上界： \[ M_ X(t) \leq \exp\left( \frac{t^2 (b-a)^2}{8} \right). \] 这一结论在证明浓度不等式时至关重要。 2. 关键思路：凸函数与线性插值 由于 \( e^{tx} \) 是凸函数，对于任意 \( x \in [ a,b ] \)，可以利用凸性将其表示为端点 \( a \) 和 \( b \) 的线性插值： \[ e^{tx} \leq \frac{b-x}{b-a} e^{ta} + \frac{x-a}{b-a} e^{tb}. \] （注：这是凸函数在区间上的弦高于曲线性质的直接应用。） 3. 利用零均值条件化简 对上述不等式两边取期望，并代入 \( \mathbb{E}[ X ] = 0 \)： \[ \mathbb{E}[ e^{tX} ] \leq \frac{b}{b-a} e^{ta} - \frac{a}{b-a} e^{tb}. \] 令 \( p = \frac{b}{b-a} \)，\( 1-p = -\frac{a}{b-a} \)，则上界化为： \[ M_ X(t) \leq p e^{ta} + (1-p) e^{tb} = e^{ta} \left[ p + (1-p) e^{t(b-a)} \right ]. \] 4. 化简为单变量函数优化 令 \( h = t(b-a) \)，\( u = -a/(b-a) \in [ 0,1 ] \)，则问题转化为最小化函数： \[ \phi(u) = \ln\left( u e^{-h} + (1-u) e^{h(1-u)} \right). \] 通过求导可证明 \( \phi(u) \) 在 \( u=1/2 \) 时取得最大值，且最大值为 \( \frac{h^2}{8} \)。详细推导需展开： 令 \( L(h) = \ln\left( \frac{e^{h} + e^{-h}}{2} \right) \)，利用泰勒展开或直接证明 \( L(h) \leq \frac{h^2}{8} \)。 最终得到 \( M_ X(t) \leq \exp\left( \frac{t^2 (b-a)^2}{8} \right) \)。 5. 应用：Hoeffding不等式的推导 对随机变量 \( X \) 应用Chernoff界（即用矩生成函数控制尾概率）： \[ P(X \geq \epsilon) \leq \inf_ {t>0} e^{-t\epsilon} M_ X(t) \leq \inf_ {t>0} \exp\left( -t\epsilon + \frac{t^2 (b-a)^2}{8} \right). \] 右侧为二次函数最小值，在 \( t = \frac{4\epsilon}{(b-a)^2} \) 处取到，代入得： \[ P(X \geq \epsilon) \leq \exp\left( -\frac{2\epsilon^2}{(b-a)^2} \right). \] 这就是Hoeffding不等式对零均值有界随机变量的形式。 6. 推广与意义 非零均值 ：若 \( \mathbb{E}[ X ] = \mu \)，可对 \( X-\mu \) 应用引理。 独立和 ：若 \( X_ 1, \dots, X_ n \) 独立且 \( a_ i \leq X_ i \leq b_ i \)，则其和的尾概率有指数衰减上界。 统计学习 ：Hoeffding不等式是机器学习中PAC理论的基础，用于分析经验风险与期望风险的偏差。 Hoeffding引理通过凸性技巧将复杂的矩生成函数问题转化为简单优化，体现了概率论中“有界性带来强控制”的核心思想。