几个概率不等式(二)Chernoff_bounds_初步_用高斯分布来演示

这个文章讲一下 Chernoff Bounds，这个限其实是一种思路，不是一种固定的限，所以，如果上网搜的话，会有各种各样的不等式都被称为 Chernoff Bounds.   另外，名称上也有叫  Chernoff-Hoeffding Bounds,  Chernoff 首先阐述了这种思想，用在抛硬币上，后来 Hoeffding 推广到更一般的情况。

这个限的思路如下：

1). 把不等式转换成 e 的指数形式，并引入一个自由变量

2). 使用 Markov 不等式

3). 应用其它各种已知的条件，例如独立性，例如其他纯数学上的不等式

4).把限看成是 t 的函数，求解以 t 为变量的这个函数的极值（求最小值，以便让上界尽可能地低）

我们以正态分布为例子来把上面的思路演示一下：

X 是满足  的随机变量，则：

我们要看的概率是：

1). 我们把上面的概率换成：

2). 使用 Markov 不等式

现在，来计算公式 (2) 中的数学期望

把公式 (3) 代入 公式 (2):

我们的目标，是让公式 (4) 中右侧尽可能地小，也就是让这个概率的上界尽可能小。

我们对公式 (4) 中右侧的指数部分，求最小值：

所以得到：

把 (6) 代入 (4) 有：

即：

我们用标准正态分布来代入看看 N(0,1)

其中 a > 0，是因为 公式 (6) 中要求 t > 0