D.4 二项分布尾部上界

设 $X_1,\dots ,X_m$ 为独立随机变量，取值在 $\{0,1\}$ 中，且 $\mathbb{P}\left[X_i=1\right]=p\in$ $\left[0,1\right]$ 对于 $i=1,\dots ,m$ 。那么，$\sum _{i=1}^m{X}_i$ 服从二项分布 $B\left(m,p\right)$ 。我们将用 $\bar{X}$ 表示平均值 $\bar{X}=\frac{1}{m}\sum _{i=1}^m{\bar{X}}_i$ 。然后，以下等式和不等式成立:

$$\mathbb{P}\left[\bar{X}-p>ϵ\right]=\sum _{k=\lceil \left(p+ϵ\right)m\rceil }^m\left(\begin{array}{c}m\\ k\end{array}\right)p^k{\left(1-p\right)}^{m-k}\text{\hspace{1em}(Binomial formula)}$$ $$\mathbb{P}\left[\bar{X}-p>ϵ\right]\le e^{-2m{ϵ}^2}\text{\hspace{1em}(Hoeffding’s inequality)}$$ $$\mathbb{P}\left[\bar{X}-p>ϵ\right]\le e^{-\frac{m{ϵ}^2}{2{\sigma }^2+\frac{2ϵ}{3}}}\text{\hspace{1em}(Bernstein’s inequality)}$$ $$\mathbb{P}\left[\overline{X}-p>ϵ\right]\le e^{-m{\sigma }^2\theta \left(\frac{ϵ}{{\sigma }^2}\right)}\text{\hspace{1em}(Bennett’s inequality)}$$ $$\mathbb{P}\left[\bar{X}-p>ϵ\right]\le e^{-m\mathrm{D}\left(p+ϵ\parallel p\right)}\text{\hspace{1em}(Sanov’s inequality,)}$$

其中 ${\sigma }^2=p\left(1-p\right)=\mathrm{Var}\left[X_i\right]$ 和 $\theta \left(x\right)=\left(1+x\right)\log \left(1+x\right)-x$ 。最后三个不等式在练习 D.6 和 D.7 中有所展示。例如，使用伯恩斯坦不等式，我们可以看到对于 $ϵ$ 相对较小，即 $ϵ\ll 2{\sigma }^2$ ，上界大致呈 $e^{-\frac{m{ϵ}^2}{2{\sigma }^2}}$ 的形式，因此表现出高斯行为。对于 $ϵ\gg 2{\sigma }^2,e^{-\frac{3mϵ}{2}}$ ，上界表现出泊松行为。

图 D.1 展示了这些界限对于不同方差 ${\sigma }^2=p\left(1-p\right)$ 的值的比较:小方差 $\left(p=.05\right)$ ，大方差 $\left(p=.5\right)$ 。