Loading [MathJax]/jax/element/mml/optable/SuppMathOperators.js

概率不等式

Inequality

Azuma-Hoeffding Inequality

Azuma-Hoeffding 不等式:设 ${Xi:i=0,1,2,\cdots}|X_k - X{k-1}| < c_k$,则

supermartingale:P(XNX0t)exp(t22Nk=1c2k)submartingale:P(XNX0t)exp(t22Nk=1c2k)martingale:P(|XNX0|t)exp(t22Nk=1c2k)

Hoeffding Inequality

Hoeffding 不等式:考虑随机变量序列 X1,X2,,XN,Xi[ai,bi]

  • 对随机变量 ˉX=1NNi=1Xi,对任意 t>0 满足

    P(ˉXEˉXt)exp(2N2t2Ni=1(biai)2)P(EˉXˉXt)exp(2N2t2Ni=1(biai)2)
  • 对随机变量 $SN = \sum{i=1}^N X_it>0$ 满足

    P(SNESN
  • 两不等式可用绝对值合并,但将不够精确

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 类实际个数