切尔诺夫界的拓展
相互独立的$r.v.$序列$X_1,X_2,…X_n$满足：
$$
Pr\left( X_i=1 \right) =Pr\left( X_i=-1 \right) =\frac{1}{2}
$$
记$X=\sum_{i=1}^n{X_i}$，则对任意的$a>0$有：
$$
Pr\left( X\ge a \right) \le e^{-a^2/2n}
$$
$Proof:$对于任意$t>0$有$\mathbb{E}\left[ e^{tX_i} \right] =\frac{1}{2}e^t+\frac{1}{2}e^{-t}$，将其$Taylor$展开得到：
$$
\mathbb{E}\left[ e^{tX_i} \right] =\sum_{i\ge 0}{\frac{t^{2i}}{\left( 2i \right) !}}\le \sum_{i\ge 0}{\frac{\left( t^2/2 \right) ^i}{\left( i \right) !}=e^{t^2/2}}
$$
故有：
$$
\mathbb{E}\left[ e^{tX} \right] =\prod_{i=1}^n{\mathbb{E}\left[ e^{tX_i} \right]}\le e^{n\cdot t^2/2}
$$
进而可以得到：
$$
Pr\left( X\ge a \right) =Pr\left( e^{tX}\ge e^{ta} \right) \le \frac{\mathbb{E}\left[ e^{tX} \right]}{e^{ta}}\le e^{n\cdot t^2/2-ta}
$$
令$t=a/n$，得到：
$$
Pr\left( X\ge a \right) \le e^{-a^2/2n}
$$
命题得证！此外，由于对称性可以得到：
$$
Pr\left( X\le -a \right) \le e^{-a^2/2n}
$$
进一步可以得到：
$$
Pr\left( \left| X \right|\ge a \right) \le 2e^{-a^2/2n}
$$
设相互独立的$r.v.$序列$Y_1,Y_2,…Y_n$满足：
$$
Pr\left( Y_i=1 \right) =Pr\left( Y_i=0 \right) =\frac{1}{2}
$$
记$Y=\sum_{i=1}^n{Y_i}$，且$\mu =\mathbb{E}\left[ Y \right] =\frac{n}{2}$，则对任意的$a>0$有：
$$
Pr\left( Y\ge \mu +a \right) \le e^{-2a^2/n}
$$
对任意的$\delta >0$有：
$$
Pr\left( Y\ge \left( 1+\delta \right) \mu \right) \le e^{-\delta ^2\mu}
$$
$Proof:$令$Y_i=\left( X_i+1 \right) /2$，引用前文的记号可以得到：
$$
Y=\sum_{i=1}^n{Y_i}=\frac{1}{2}\sum_{i=1}^n{X_i}+\frac{n}{2}=\frac{1}{2}X+\mu
$$
应用前文定理可以得到：
$$
Pr\left( Y\ge \mu +a \right) =Pr\left( X>2a \right) \le e^{-4a^2/2n}=e^{-2a^2/n}
$$
令$a=\delta \mu =\frac{\delta n}{2}$，应用前文定理可以得到：
$$
Pr\left( Y\ge \left( 1+\delta \right) \mu \right) =Pr\left( X>2\delta \mu \right) \le e^{-4\delta ^2\mu ^2/2n}=e^{-\delta ^2\mu}
$$
类似的可以得到：
对任意的$0 < a < \mu $有： $$ Pr\left( Y\ge \mu -a \right) \le e^{-2a^2/n} $$ 对任意的$0<\delta <1$有： $$ Pr\left( Y\ge \left( 1-\delta \right) \mu \right) \le e^{-\delta ^2\mu} $$
切尔诺夫界的应用
记$\tilde{p}$为二项分布参数$p$的估计值，则对于任意$\delta >0$都有：
上式中最终结果与$p$相关，但是实际$p$是未知的，故此界并无实际意义。但是由于$p\le 1$可以得到一个简单解：
$$
Pr\left[ \left| \hat{p}-p \right|\ge \delta \right] \le =exp\left\{ -n\delta ^2/2 \right\} +exp\left\{ -n\delta ^2/3 \right\}
$$
即可称区间$\left[ \tilde{p}-\delta ,\tilde{p}+\delta \right] $为参数$p$的置信度为$1-e^{-n\delta ^2/2}+e^{-n\delta ^2/3}$的置信区间。
