D.3 乘法 Chernoff 界限

Sanov定理可以用来证明以下乘法Chernoff界限。

定理D.4(乘法Chernoff界限)$Let{X}_1,\dots ,X_{m}beindependentrandomvari$ - ables根据某个分布 $\mathcal{D}$ 抽取，该分布的平均值为 $p$ 且支撑集包含在 $\left[0,1\right]$ 中。那么，对于任何 $\gamma \in \left[0,\frac{1}{p}-1\right]$ ，以下不等式对于 $\hat{p}=\frac{1}{m}\sum _{i=1}^m{X}_i$ 成立:

$$\mathbb{P}\left[\hat{p}\ge \left(1+\gamma \right)p\right]\le e^{-\frac{mp{\gamma }^2}{3}}$$ $$\mathbb{P}\left[\hat{p}\le \left(1-\gamma \right)p\right]\le e^{-\frac{mp{\gamma }^2}{2}}.$$

证明:证明包括在每个情况下推导出比Pinsker不等式更精细的二进制相对熵的下界。使用不等式 $\log \left(1+x\right)\ge \frac{x}{1+\frac{x}{2}}$ 和 $\log \left(1+x\right)<x$ ，我们可以写出

$$-\mathrm{D}\left(\left(1+\gamma \right)p\parallel p\right)=\left(1+\gamma \right)p\log \frac{p}{\left(1+\gamma \right)p}+\left(1-\left(1+\gamma \right)p\right)\log \left[\frac{1-p}{1-\left(1+\gamma \right)p}\right]$$ $$=\left(1+\gamma \right)p\log \frac{1}{1+\gamma }+\left(1-p-\gamma p\right)\log \left[1+\frac{\gamma p}{1-p-\gamma p}\right]$$ $$\le \left(1+\gamma \right)p\frac{-\gamma }{1+\frac{\gamma }{2}}+\left(1-p-\gamma p\right)\frac{\gamma p}{1-p-\gamma p}$$ $$=\gamma p\left[1-\frac{1+\gamma }{1+\frac{\gamma }{2}}\right]=\frac{-\frac{{\gamma }^{2}p}{2}}{1+\frac{\gamma }{2}}=\frac{-{\gamma }^{2}p}{2+\gamma }$$ $$\le \frac{-{\gamma }^{2}p}{2+1}=\frac{-{\gamma }^{2}p}{3}$$

类似地，使用对于 $x\in \left(0,1\right)$ 和 $\log \left(1-x\right)<-x$ 有效的 $\left(1-x\right)\log \left(1-x\right)\ge -x+\frac{x^2}{2}$ 不等式，我们可以写出

$$-\mathrm{D}\left(\left(1-\gamma \right)p\parallel p\right)=\left(1-\gamma \right)p\log \frac{p}{\left(1-\gamma \right)p}+\left(1-\left(1-\gamma \right)p\right)\log \left[\frac{1-p}{1-\left(1-\gamma \right)p}\right]$$ $$=\left(1-\gamma \right)p\log \frac{1}{1-\gamma }+\left(1-p+\gamma p\right)\log \left[1-\frac{\gamma p}{1-p+\gamma p}\right]$$ $$\le \left(\gamma -\frac{{\gamma }^2}{2}\right)p+\left(1-p+\gamma p\right)\frac{-\gamma p}{1-p+\gamma p}=\frac{-{\gamma }^{2}p}{2}.$$

这完成了证明。