关于伯恩斯坦不等式变形推导的技术疑问
关于伯恩斯坦不等式变形推导的技术疑问
嘿,这个问题其实只需要一步简单的变量替换就能搞明白,我给你拆解清楚:
首先先把原不等式再明确一下(来自Vershynin《High-Dimensional Probability》的推论2.8.3):
设$X_1, \dots, X_N$是独立、零均值的次指数随机变量,对任意$t \geq 0$,有
$$ \mathbb{P}\left(\left|\frac{1}{N} \sum_{i=1}^N X_i\right| \geq t\right) \leq 2 \exp\left(-c \min\left{ \frac{t2}{K2}, \frac{t}{K} \right} N \right) $$
其中$ K = \max_i |X_i|_{\phi_2}$,$c > 0$是绝对常数。
现在我们要推导的是当$t \geq 1$时的那个变形,核心就是把原不等式里的$t$替换成$tK$:
- 令原不等式中的阈值为$t' = tK$,代入后左边就变成了你要的概率项:$\mathbb{P}\left(\left|\frac{1}{N} \sum_{i=1}^N X_i\right| \geq tK\right)$
- 再看右边指数里的$\min$部分:
- 计算第一项:$\frac{(t')2}{K2} = \frac{(tK)2}{K2} = t^2$
- 计算第二项:$\frac{t'}{K} = \frac{tK}{K} = t$
- 因为题目限定了$t \geq 1$,此时$t^2 \geq t$(毕竟$t(t-1) \geq 0$),所以$\min{t^2, t} = t$
- 把这个结果代回原不等式的右边,就得到了:$2 \exp(-c \cdot t \cdot N)$
说白了,这个变形就是把“绝对偏差”转换成了以$K$为单位的归一化偏差,而$t \geq 1$的条件刚好让$\min$函数取到线性项,从而得到你想要的指数衰减形式。如果$t < 1$的话,$\min$就会取平方项,结果就不一样啦。
备注:内容来源于stack exchange,提问作者LSK21




