几个概率不等式(三) Chernoff_bounds_用于泊松过程
这个文章讲一下基于泊松过程推导一下 Chernoff-Hoeffding Bounds.
定义随机变量:
要求上面的随机变量相互独立。
定义随机变量:
则我们想知道如下这个概率:
其中 m 大于 X 的均值(数学期望),小于等于 n.
下面展开推导过程,具体细节会在视频中讲解。
其中: t > 0
其中:
把公式 (3) 代入公式 (2):
用 Arithmatic Mean/Geometric Mean Inequality (算术几何平均不等式):
其中 :
把公式 (5) 代入公式 (4) :
公式 (6) 代入公式 (1):
求公式 (7) 右边的最小值:
经过推导有:
所以:
把公式 (8) 和 (9) 代入 (7):
把公式 (10) 写成不是 e 的指数的形式: