这个文章讲一下基于泊松过程推导一下 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 的指数的形式:

关键词：