UA MATH567 高维统计I 概率不等式10 Bernstein不等式

UA MATH567 高维统计I 概率不等式10 Bernstein不等式

我们在介绍亚高斯分布后介绍了适用于亚高斯分布的推广的Hoeffding不等式，对于亚指数分布，我们可以得到类似的不等式。因为亚指数分布相对更具有一般性，因此亚指数分布的这个概率不等式是一个适用性比较广的不等式。

Bernstein不等式 版本1 假设$\{X_i{\}}_{i=1}^N$是一列零均值独立亚指数随机变量，$\forall t>0$, $K={\max }_{1\le i\le N}{\Vert X_i\Vert }_{{\psi }_1}$
$$P\left(\left|\sum _{i=1}^N{X}_i\right|\ge t\right)\le 2\exp \left(-c\min \left(\frac{t}{K},\frac{t^2}{{\sum }_{i=1}^N{\Vert X_i\Vert }_{{\psi }_1}^2}\right)\right)$$

其中$c$是一个常数。

证明
我们先用Markov不等式讨论$P({\sum }_{i=1}^N{X}_i\ge t)$,
$$\begin{gathered} P(\sum _{i=1}^N{X}_i\ge t)=P(e^{\lambda {\sum }_{i=1}^N{X}_i}\ge e^{\lambda t}) \\ \le e^{-\lambda t}E{e}^{\lambda {\sum }_{i=1}^N{X}_i}=e^{-\lambda t}\prod _{i=1}^{N}E{e}^{\lambda X_i} \end{gathered}$$

根据亚指数性5，$K_5=c{\Vert X_i\Vert }_{{\psi }_1}$
$$E{e}^{\lambda X_i}\le e^{c^2{\Vert X_i\Vert }_{{\psi }_1}^2{\lambda }^2},\forall 0<\lambda \le 1/K_5$$

要使对所有的$i$，上式均适用，我们需要进一步限制$\lambda$的取值为
$$0<\lambda \le \frac{1}{c{\max }_i{\Vert X\Vert }_{{\psi }_1}}$$

于是
$$\begin{gathered} e^{-\lambda t}\prod _{i=1}^{N}E{e}^{\lambda X_i}\le e^{-\lambda t}\prod _{i=1}^N{e}^{c^2{\Vert X_i\Vert }_{{\psi }_1}^2{\lambda }^2} \\ =\exp (-\lambda t+c^2{\lambda }^2\sum _{i=1}^N{\Vert X_i\Vert }_{{\psi }_1}^2) \end{gathered}$$

接下来，我们要选择一个$\lambda$使得这个上界最小，即我们需要解
$$\underset{0<\lambda \le \frac{1}{c{\max }_i{\Vert X\Vert }_{{\psi }_1}}}{\min }-\lambda t+c^2{\lambda }^2\sum _{i=1}^N{\Vert X_i\Vert }_{{\psi }_1}^2$$

这个二次函数的最小值要么在全局最小点处取得，要么在边界上取得，即
$$\lambda =\frac{1}{c{\max }_i{\Vert X\Vert }_{{\psi }_1}}or\frac{t}{2c^2{\sum }_{i=1}^N{\Vert X_i\Vert }_{{\psi }_1}^2}$$

于是最小的上界为
$$\exp \left(-c\min \left(\frac{t}{K},\frac{t^2}{{\sum }_{i=1}^N{\Vert X_i\Vert }_{{\psi }_1}^2}\right)\right)$$

对于$P(-{\sum }_{i=1}^N{X}_i\ge t)$，我们可以得到一样的结果，这样就说明了Bernstein不等式 版本1。

---

Bernstein不等式 版本2 假设$\{X_i{\}}_{i=1}^N$是一列零均值独立亚指数随机变量，$a$是一个常向量，$\forall t>0$, $K={\max }_{1\le i\le N}{\Vert X_i\Vert }_{{\psi }_1}$
$$P\left(\left|\sum _{i=1}^N{a}_i{X}_i\right|\ge t\right)\le 2\exp \left(-c\min \left(\frac{t}{K{\Vert a\Vert }_{\infty }},\frac{t^2}{K^2{\Vert a\Vert }_2^2}\right)\right)$$

其中$c$是一个常数。

说明 我们简单比较一下版本1和版本2，版本2试图讨论的是$X_i$的线性组合，我们可以找到版本1和2上界的对应关系。

根据亚指数范数的正齐次性
$$\sum _{i=1}^N{\Vert a_i{X}_i\Vert }_{{\psi }_1}^2=\sum _{i=1}^N{a}_i^2{\Vert X_i\Vert }_{{\psi }_1}^2\le \sum _{i=1}^N{a}_i^2{K}^2=K^2{\Vert a\Vert }_2^2$$

这体现了版本1中上界$\frac{t^2}{{\sum }_{i=1}^N{\Vert X_i\Vert }_{{\psi }_1}^2}$与$\frac{t^2}{K^2{\Vert a\Vert }_2^2}$的对应关系。

同样根据亚指数范数的正齐次性
$$\underset{i}{\max }{\Vert a_i{X}_i\Vert }_{{\psi }_1}=\underset{i}{\max }|a_i|{\Vert X_i\Vert }_{{\psi }_1}\le {\Vert a\Vert }_{\infty }K$$

这体现了版本1中上界$\frac{t}{K}$与$\frac{t}{K{\Vert a\Vert }_{\infty }}$的对应关系。

如果取$a_i=1/N$，我们可以得到关于样本均值的不等式：

Bernstein不等式 版本3 假设$\{X_i{\}}_{i=1}^N$是一列零均值独立亚指数随机变量，$\forall t>0$, $K={\max }_{1\le i\le N}{\Vert X_i\Vert }_{{\psi }_1}$
$$P\left(\left|\bar{X}\right|\ge t\right)\le 2\exp \left(-cN\min \left(\frac{t}{K},\frac{t^2}{K^2}\right)\right)$$

其中$c$是一个常数。

---

Bernstein不等式 版本4 假设$\{X_i{\}}_{i=1}^N$是一列零均值独立亚指数上界为$K$的随机变量，$\forall t>0$,
$$P\left(\left|\sum _{i=1}^N{X}_i\right|\ge t\right)\le 2\exp \left(-\frac{t^2/2}{{\sigma }^2+Kt/3}\right)$$

${\sigma }^2={\sum }_{i=1}^{N}E{X}_i^2$。这是使用最广泛的一个版本，因为它能提供一个比Hoeffding不等式更小的上界。

总结

以上是生活随笔为你收集整理的UA MATH567 高维统计I 概率不等式10 Bernstein不等式的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。