大家好，欢迎来到IT知识分享网。
Hoeffding不等式证明见Hoeffding不等式证
鞅的定义：
一个随机过程 { Z n , n ≥ 1 } \{Z_n,n\ge 1\} {
Zn,n≥1},若对一切 n n n有
E [ ∣ Z n ∣ ] < ∞ \mathbb{E}[|Z_n|] \lt \infty E[∣Zn∣]<∞
且
E [ Z n + 1 ∣ Z 1 , ⋯ , Z n ] = Z n \mathbb{E}[Z_{n+1} |Z_1,\cdots,Z_n] = Z_n E[Zn+1∣Z1,⋯,Zn]=Zn
鞅是公平博弈的广义版本。若我们将 Z n Z_n Zn解释为一个赌徒经过 n n n轮公平博弈后得到的财产为 Z n Z_n Zn，则下一次赌博得到的财产 Z n + 1 Z_{n+1} Zn+1期望等于 Z n Z_n Zn而不管前面发生了什么
例子： X i X_i Xi是均值为0的独立同分布变量, S n = ∑ i = 1 n X i S_{n}=\sum_{i=1}^n X_i Sn=∑i=1nXi为一个鞅
在介绍Azuma不等式前，先介绍一个引理
引理1：随机变量 X X X有 E [ X ] = 0 \mathbb{E}[X]=0 E[X]=0且 P { − α ≤ X ≤ β } = 1 P\{-\alpha \le X \le \beta\} = 1 P{
−α≤X≤β}=1则对任意凸函数有
E [ f ( X ) ] ≤ β α + β f ( − α ) + α α + β f ( β ) \mathbb{E}[f(X)] \le \frac{\beta}{\alpha + \beta}f(-\alpha) + \frac{\alpha}{\alpha + \beta}f(\beta) E[f(X)]≤α+ββf(−α)+α+βαf(β)
证明：由凸函数的定义, ∀ γ ∈ [ 0 , 1 ] \forall \gamma\in [0,1] ∀γ∈[0,1], x , y x,y x,y为定义域中的点,有
f ( γ x + ( 1 − γ ) y ) ≤ γ f ( x ) + ( 1 − γ ) f ( y ) f(\gamma x + (1-\gamma)y) \le \gamma f(x) + (1-\gamma) f(y) f(γx+(1−γ)y)≤γf(x)+(1−γ)f(y)
即可得到
引理2 对 0 ≤ θ ≤ 1 0\le \theta \le 1 0≤θ≤1有
θ e ( 1 − θ ) x + ( 1 − θ ) e − θ x ≤ e x 2 / 8 \theta e^{(1-\theta)x} +(1-\theta)e^{-\theta x} \le e^{x^2/8} θe(1−θ)x+(1−θ)e−θx≤ex2/8
证明：令 θ = ( 1 + α ) / 2 , x = 2 β \theta = (1+\alpha) / 2,x=2\beta θ=(1+α)/2,x=2β，则相当于证明对 − 1 ≤ α ≤ 1 -1\le \alpha\le1 −1≤α≤1有
( 1 + α ) e β ( 1 − α ) + ( 1 − α ) e − β ( 1 + α ) ≤ 2 e β 2 / 2 (1+\alpha) e^{\beta (1-\alpha)} + (1-\alpha) e^{-\beta(1+\alpha)} \le 2 e^{\beta^2/2} (1+α)eβ(1−α)+(1−α)e−β(1+α)≤2eβ2/2
等价于
e β + e − β + α ( e β − e − β ) ≤ 2 exp { α β + β 2 / 2 } e^\beta + e^{-\beta} + \alpha(e^\beta – e^{-\beta}) \le 2 \exp\{\alpha\beta + \beta^2 /2\} eβ+e−β+α(eβ−e−β)≤2exp{
αβ+β2/2}
当 α = ± 1 \alpha=\pm 1 α=±1或者 β \beta β足够大，比如 β ≥ 100 \beta \ge100 β≥100时，不等式显然成立
所以如果不等式不成立，则函数
f ( α , β ) = e β + e − β + α ( e β − e − β ) − 2 exp { α β + β 2 / 2 } f(\alpha,\beta)=e^\beta +e^{-\beta} +\alpha(e^\beta – e^{-\beta}) -2\exp\{ \alpha \beta + \beta^2 /2\} f(α,β)=eβ+e−β+α(eβ
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/150300.html
