切诺夫界（Chernoff Bound）形式及其证明-Toy模板网

这篇具有很好参考价值的文章主要介绍了切诺夫界（Chernoff Bound）形式及其证明。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

马尔可夫不等式

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

$p roo f .$

设非负随机变量 $X$ 的概率密度函数为 $f (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}$
所以 $\ge \xi P(X \ge \xi)$

经变换得到结论：
$\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$

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

$p roo f .$

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

$lemma\ 1:$

设随机变量 $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^{sX_i})=\prod_{i=1}^{n}E(e^{sX_i})=\prod_{i=1}^{n}M_{X_i}(s)$

即：
$M_X(s)=\prod_{i=1}^{n}M_{X_i}(s)$
$lemma\ 2$ ：

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

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

因为 $e^x \ge 1+x$ ，得到结论
$M_X(s) \le e^{p(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}$
令 $s=ln(1+\delta)$

可得：
$\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 \gt 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}$
所以上尾得证：
$\le (1+\delta)\mu) \le e^{-\frac{\delta^2}{2+\delta}\mu}$

下尾类似：

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

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

非伯努利切诺夫界

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

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

上尾：
$\ge (1+\delta)\mu) \le e^{-\frac{2\delta^2\mu^2}{n(b-a)^2}}$
下尾：
$\le (1-\delta)\mu) \le e^{-\frac{\delta^2\mu^2}{n(b-a)^2}}$ 文章来源地址https://www.toymoban.com/news/detail-769779.html