概率不等式
Inequality
Azuma-Hoeffding Inequality
Azuma-Hoeffding 不等式:设 ${Xi:i=0,1,2,\cdots}是鞅差序列,且|X_k - X{k-1}| < c_k$,则
super−martingale:P(XN−X0≥t)≤exp(−t22∑Nk=1c2k)sub−martingale:P(XN−X0≤−t)≤exp(−t22∑Nk=1c2k)martingale:P(|XN−X0|≥t)≤exp(−t22∑Nk=1c2k)Hoeffding Inequality
Hoeffding 不等式:考虑随机变量序列 X1,X2,⋯,XN,Xi∈[ai,bi]
对随机变量 ˉX=1N∑Ni=1Xi,对任意 t>0 满足
P(ˉX−EˉX≥t)≤exp(−2N2t2∑Ni=1(bi−ai)2)P(EˉX−ˉX≥t)≤exp(−2N2t2∑Ni=1(bi−ai)2)对随机变量 $SN = \sum{i=1}^N X_i,对任意t>0$ 满足
P(SN−ESN⩾
- 两不等式可用绝对值合并,但将不够精确
Bretagnolle-Huber-Carol Inequility
Bretagnolle-Huber-Carol 不等式:{X_i: i=1,2,\cdots,N} i.i.d. M(p1, p_2, \cdots, p_k) 服从类别为 k 的多项分布
- N_i:第 i 类实际个数