切诺夫界（Chernoff Bound）形式及其证明

马尔可夫不等式

设随机变量X的取值为非负数，马尔可夫不等式形式为：
$$P(X\ge \xi )\le \frac{E(X)}{\xi }$$

$proof.$

设非负随机变量$X$的概率密度函数为$f(x)$
E ( X ) = ∫ 0 ∞ x f ( x ) d x = ∫ 0 ξ x f ( x ) d x + ∫ ξ ∞ x f ( x ) d x ≥ ∫ ξ ∞ x f ( x ) d x ≥ ∫ ξ ∞ ξ f ( x ) d x = ξ P ( X ≥ ξ )

$$\begin{split} E(X)&=\int_{0}^{\infty}xf(x)dx \\ &= \int_{0}^{\xi}xf(x)dx+\int_{\xi}^{\infty}xf(x)dx \\ &\ge \int_{\xi}^{\infty}xf(x)dx \\ &\ge \int_{\xi}^{\infty}\xi f(x)dx \\ &= \xi P(X \ge \xi) \end{split}$$ E(X)​=∫0∞​xf(x)dx=∫0ξ​xf(x)dx+∫ξ∞​xf(x)dx≥∫ξ∞​xf(x)dx≥∫ξ∞​ξf(x)dx=ξP(X≥ξ)​
所以$E(X)\ge \xi P(X\ge \xi )$

经变换得到结论：
$$P(X\ge \xi )\le \frac{E(X)}{\xi }$$

切诺夫界

令$X={\sum }_{i=1}^n{X}_i$，其中$X_1,\dots ,X_n$之间相互独立，并且$P(X_i=1)=p_i,P(X_i=0)=1-p_i$

令$\mu =E(X)={\sum }_{i=1}^n{p}_i$

1. Upper Tail:
   $$\forall \delta >0,P(X\ge (1+\delta )\mu )\le e^{-\frac{{\delta }^2}{2+\delta }\mu }$$

2. Lower Tail:
   $$\forall 0<\delta <1,P(X\le (1-\delta )\mu )\le e^{-\frac{{\delta }^2}{2}\mu }$$

$proof.$

由马尔可夫不等式可知，设$X$为一非负随机变量，对于$\forall s>0$
$$P(X\ge a)=P(e^{sX}\ge e^{sa})\le \frac{E(e^{sX})}{e^{sa}}$$
类似可知
$$P(X\le a)=P(e^{-sX}\ge e^{-sa})\le \frac{E(e^{-sX})}{e^{-sa}}$$
现令$M_X(s)=E(e^{sX})$

$lemma1:$

设随机变量$X={\sum }_{i=1}^n{X}_i$

$M_X(s)=E(e^{sX})=E(e^{s{\sum }_{i=1}^n{X}_i})=E({\prod }_{i=1}^n{e}^{s{X}_i})={\prod }_{i=1}^{n}E(e^{s{X}_i})={\prod }_{i=1}^n{M}_{X_i}(s)$

即：
$$M_X(s)=\prod _{i=1}^n{M}_{X_i}(s)$$
$lemma2$：

设随机变量$X\sim B(p,1)$

$M_X(s)=p{e}^s+(1-p)=1+p(e^s-1)$

因为$e^x\ge 1+x$，得到结论
$$M_X(s)\le e^{p(e^s-1)}$$
上尾证明：
P ( X ≤ ( 1 + δ ) μ ) ≤ E ( e s X ) e s ( 1 + δ ) μ = M X ( s ) e s ( 1 + δ ) μ = ∏ i = 1 n M X i ( s ) e s ( 1 + δ ) μ ≤ ∏ i = 1 n e p i ( e s − 1 ) e s ( 1 + δ ) μ = e ( e s − 1 ) ∑ i = 1 n p i e s ( 1 + δ ) μ = e ( e s − 1 ) μ e s ( 1 + δ ) μ = [ e ( e s − 1 ) e s ( 1 + δ ) ] μ

$$\begin{split} P(X \le (1+\delta)\mu) &\le \frac{E(e^{sX})}{e^{s(1+\delta)\mu}} \\ &=\frac{M_X(s)}{e^{s(1+\delta)\mu}} \\ &=\frac{\prod_{i=1}^{n} M_{X_i}(s)}{e^{s(1+\delta)\mu}} \\ &\le \frac{\prod_{i=1}^{n} e^{p_i(e^s-1)}}{e^{s(1+\delta)\mu}} \\ &= \frac{e^{(e^s-1)\sum_{i=1}^{n}p_i}}{e^{s(1+\delta)\mu}} \\ &= \frac{e^{(e^s-1)\mu}}{e^{s(1+\delta)\mu}} \\ &= \left[\frac{e^{(e^s-1)}}{e^{s(1+\delta)}}\right]^\mu \\ \end{split}$$ P(X≤(1+δ)μ)​≤es(1+δ)μE(esX)​=es(1+δ)μMX​(s)​=es(1+δ)μ∏i=1n​MXi​​(s)​≤es(1+δ)μ∏i=1n​epi​(es−1)​=es(1+δ)μe(es−1)∑i=1n​pi​​=es(1+δ)μe(es−1)μ​=[es(1+δ)e(es−1)​]μ​
令$s=ln(1+\delta )$

可得：
$$P(X\le (1+\delta )\mu )\le {\left(\frac{e^{\delta }}{(1+\delta {)}^{(1+\delta )}}\right)}^{\mu }$$
又有：$ln\left[{\left(\frac{e^{\delta }}{(1+\delta {)}^{(1+\delta )}}\right)}^{\mu }\right]=\mu (\delta -(1+\delta )ln(1+\delta ))$，且$\forall x>0,ln(1+x)\ge \frac{x}{1+\frac{x}{2}}$

可得：
$$\mu (\delta -(1+\delta )ln(1+\delta ))\le -\frac{{\delta }^2}{2+\delta }\mu$$
即：
$${\left(\frac{e^{\delta }}{(1+\delta {)}^{(1+\delta )}}\right)}^{\mu }\le e^{-\frac{{\delta }^2}{2+\delta }\mu }$$
所以上尾得证：
$$P(X\le (1+\delta )\mu )\le e^{-\frac{{\delta }^2}{2+\delta }\mu }$$

下尾类似：

令$s=ln(1-\delta )$

且使用不等式：$\forall 0<\delta <1,ln(1+\delta )\ge -\delta +\frac{{\delta }^2}{2}$

非伯努利切诺夫界

在上述切诺夫界中，假设了$X_i\sim B(p_i,1)$，对于不服从伯努利分布的随机变量，同样有

令$X_1,\dots ,X_n$相互独立，其中$a\le X_i\le b$，令$X={\sum }_{i=1}^n{X}_i,\mu =E(X),\forall \delta >0$有：

上尾：
$$P(X\ge (1+\delta )\mu )\le e^{-\frac{2{\delta }^2{\mu }^2}{n(b-a{)}^2}}$$
下尾：
$$P(X\le (1-\delta )\mu )\le e^{-\frac{{\delta }^2{\mu }^2}{n(b-a{)}^2}}$$