概率不等式

Inequality

Azuma-Hoeffding Inequality

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

Hoeffding Inequality

Hoeffding 不等式:考虑随机变量序列 $X_1, X_2, \cdots, X_N, X_i \in [a_i, b_i]$

  • 对随机变量 $\bar X = \frac 1 N \sum_{i=1}^N {X_i}$,对任意 $t>0$ 满足

  • 对随机变量 $SN = \sum{i=1}^N X_i$,对任意 $t>0$ 满足

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

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

UBeaRLy

Posted on

2019-03-26

Updated on

2021-07-19

Licensed under

Comments