這個(gè)文章講一下 Chernoff Bounds，這個(gè)限其實(shí)是一種思路，不是一種固定的限，所以，如果上網(wǎng)搜的話，會(huì)有各種各樣的不等式都被稱為 Chernoff Bounds.? ?另外，名稱上也有叫? Chernoff-Hoeffding Bounds,? Chernoff 首先闡述了這種思想，用在拋硬幣上，后來(lái) Hoeffding 推廣到更一般的情況。

這個(gè)限的思路如下：

1). 把不等式轉(zhuǎn)換成 e 的指數(shù)形式，并引入一個(gè)自由變量

2). 使用 Markov 不等式

3). 應(yīng)用其它各種已知的條件，例如獨(dú)立性，例如其他純數(shù)學(xué)上的不等式

4).把限看成是 t 的函數(shù)，求解以 t 為變量的這個(gè)函數(shù)的極值（求最小值，以便讓上界盡可能地低）

我們以正態(tài)分布為例子來(lái)把上面的思路演示一下：

X 是滿足 ?的隨機(jī)變量，則：

我們要看的概率是：

1). 我們把上面的概率換成：

2). 使用 Markov 不等式

現(xiàn)在，來(lái)計(jì)算公式 (2) 中的數(shù)學(xué)期望

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

我們的目標(biāo)，是讓公式 (4) 中右側(cè)盡可能地小，也就是讓這個(gè)概率的上界盡可能小。

我們對(duì)公式 (4) 中右側(cè)的指數(shù)部分，求最小值：

所以得到：

把 (6) 代入 (4) 有：

即：

我們用標(biāo)準(zhǔn)正態(tài)分布來(lái)代入看看 N(0,1)

其中 a > 0，是因?yàn)?公式 (6) 中要求 t > 0