UA MATH567 高维统计I 概率不等式11 Azuma不等式
UA MATH567 高维统计I 概率不等式11 Azuma不等式
前十一讲介绍的不等式的理论基础都是Markov不等式，根据Markov不等式我们导出了Chebyshev不等式、Hoeffding不等式、Chernoff不等式、推广的Hoeffding不等式、Khintchine不等式与Bernstein不等式，并发展了用来表示一类具有相同concentration performance的分布族的方法：亚高斯分布、亚指数分布、以及更一般的Orlicz空间与Orlicz范数方法。
从这一讲开始，我们介绍另外两种导出概率不等式的方法：鞅差序列法、Lipschitz函数法，鞅差序列法可以放松独立性的假设，而Lipschitz函数法在后续介绍随机向量、随机矩阵等结构的时候具有非常重要的作用。这一讲我们先介绍用鞅差序列法+Markov不等式导出Azuma不等式。
Azuma不等式
假设(Xj,Fj)(X_j,\mathcal{F}_j)(Xj,Fj)是一个鞅差序列，即
简单起见，我们定义Fj=σ({X1,⋯,Xj})\mathcal{F}_j = \sigma(\{X_1,\cdots,X_j\})Fj=σ({X1,⋯,Xj})。假设∣Xj∣≤1,a.s.|X_j| \le 1,a.s.∣Xj∣≤1,a.s.，则∀λ>0\forall \lambda>0∀λ>0，Sn=X1+⋯+XnS_n=X_1 + \cdots + X_nSn=X1+⋯+Xn满足
P(∣Sn∣≥λn)≤Ce−cλ2P(|S_n| \ge \lambda \sqrt{n}) \le Ce^{-c\lambda^2}P(∣Sn∣≥λn)≤Ce−cλ2
其中C,cC,cC,c是两个正的常数。
说明
我们计算EetSnEe^{tS_n}EetSn，其中Sn=Sn−1+XnS_n=S_{n-1}+X_nSn=Sn−1+Xn，
EetSn=EetSn−1etXnEe^{tS_n}=Ee^{tS_{n-1}}e^{tX_n}EetSn=EetSn−1etXn
需要注意的是Sn−1S_{n-1}Sn−1与XnX_nXn并不独立，所以不能把这个乘积的期望分开，但是我们可以用条件概率表示，记
Yn=E[etSn−1etXn∣Fn−1]Y_n=E[e^{tS_{n-1}}e^{tX_n}|\mathcal{F}_{n-1}]Yn=E[etSn−1etXn∣Fn−1]
则EetSn=E[Yn]Ee^{tS_n}=E[Y_n]EetSn=E[Yn]。因为
Yn=E[etSn−1etXn∣Fn−1]=etSn−1E[etXn∣Fn−1]EYn=EetSn−1E[etXn∣Fn−1]Y_n=E[e^{tS_{n-1}}e^{tX_n}|\mathcal{F}_{n-1}]=e^{tS_{n-1}}E[e^{tX_n}|\mathcal{F}_{n-1}] \\ EY_n = Ee^{tS_{n-1}}E[e^{tX_n}|\mathcal{F}_{n-1}]Yn=E[etSn−1etXn∣Fn−1]=etSn−1E[etXn∣Fn−1]EYn=EetSn−1E[etXn∣Fn−1]
根据有界的随机变量的Chernoff不等式（∣Xn∣≤1,a.s.|X_n| \le 1,a.s.∣Xn∣≤1,a.s.），
E[etXn∣Fn−1]≤ec1t2,∃c1>0E[e^{tX_n}|\mathcal{F}_{n-1}] \le e^{c_1t^2},\exists c_1>0E[etXn∣Fn−1]≤ec1t2,∃c1>0
所以
EYn≤ec1t2EetSn−1EY_n \le e^{c_1t^2}Ee^{tS_{n-1}}EYn≤ec1t2EetSn−1
这样就得到了一个可以递归的不等式，于是
EYn≤e∑i=1ncint2,∃ci>0EY_n \le e^{\sum_{i=1}^n c_int^2},\exists c_i >0EYn≤e∑i=1ncint2,∃ci>0
记C=∑i=1nciC=\sum_{i=1}^n c_iC=∑i=1nci，根据Markov不等式，
P(Sn≥λn)≤e−tλnEYn≤eCnt2−tλnP(S_n \ge \lambda \sqrt{n}) \le e^{-t\lambda \sqrt{n}}EY_n \le e^{Cnt^2-t\lambda \sqrt{n}}P(Sn≥λn)≤e−tλnEYn≤eCnt2−tλn
我们可以选择一个ttt来最小化这个上界，考虑
t=λn2Cnt = \frac{\lambda \sqrt{n}}{2Cn}t=2Cnλn
则最小的上界为
Cnt2−tλn=Cnλ2n4C2n2−λ2n2Cn=e−λ24CCnt^2-t\lambda \sqrt{n}=Cn\frac{\lambda^2n}{4C^2n^2}-\frac{\lambda^2n}{2Cn}=e^{-\frac{\lambda^2}{4C}}Cnt2−tλn=Cn4C2n2λ2n−2Cnλ2n=e−4Cλ2
于是
P(Sn≥λn)≤e−λ24CP(S_n \ge \lambda \sqrt{n}) \le e^{-\frac{\lambda^2}{4C}}P(Sn≥λn)≤e−4Cλ2
对于P(Sn≤−λn)=P(−Sn≥λn)P(S_n \le -\lambda \sqrt{n})=P(-S_n \ge \lambda \sqrt{n})P(Sn≤−λn)=P(−Sn≥λn)也可以做类似的讨论。
评注
Azuma不等式与Bernstein不等式相比，它不需要独立性的假设，取而代之的是鞅差序列的假设，鞅差序列是在研究非独立随机变量序列常用的假设，Azuma不等式的意义在于即使没有独立性的假设，对于几乎必然有界的随机变量，e−cλ2e^{-c\lambda^2}e−cλ2的尾部概率性质也是成立的。
总结
以上是生活随笔为你收集整理的UA MATH567 高维统计I 概率不等式11 Azuma不等式的全部内容，希望文章能够帮你解决所遇到的问题。
- 上一篇： UA MATH563 概率论的数学基础
- 下一篇： [概统]本科二年级 概率论与数理统计 第