D.2 Sanov 定理

在这里，我们提出了一个比 Hoeffding 不等式更精细的上界，该上界用二元相对熵表示。

定理 D. 3(Sanov 定理)设 $X_1,\dots ,X_m$ 为独立随机变量，根据某个分布 $\mathcal{D}$ 抽取，具有均值 $p$ 且支撑集包含在 $\left[0,1\right]$ 内。那么，对于任意 $q\in \left[0,1\right]$ ，以下不等式对 $\hat{p}=\frac{1}{m}\sum _{i=1}^m{X}_i$ 成立:

$$\mathbb{P}\left[\hat{p}\ge q\right]\le e^{-m\mathrm{D}\left(q\parallel p\right)}$$

其中 $\mathrm{D}\left(q\parallel p\right)=q\log \frac{q}{p}+\left(1-q\right)\log \frac{1-q}{1-p}$ 是 $p$ 和 $q$ 的二元相对熵。

对于任意 $t>0$ ，由于函数 $x\mapsto e^{tx}$ 的凸性，以下不等式对所有 $x\in \left[0,1\right]:e^{tx}=e^{t\left[\left(1-x\right)\cdot 0+x\cdot 1\right]}\le 1-x+e^{t}x$ 成立。鉴于这一点，对于任意 $t>0$ ，我们可以写出

$$\mathbb{P}\left[\hat{p}\ge q\right]=\mathbb{P}\left[e^{tm\hat{p}}\ge e^{tmq}\right]$$ $$=\mathbb{P}\left[e^{tm\hat{p}}\ge e^{tmq}\right]$$ $$\le e^{-tmq}\mathbb{E}\left[e^{tm}\hat{p}\right]\text{(by Markov’s inequality)}$$ $$=e^{-tmq}\mathbb{E}\left[e^{t\sum _{i=1}^m{X}_i}\right]$$ $$=e^{-tmq}\prod _{i=1}^m\mathbb{E}\left[e^{t{X}_i}\right]$$ $$\le e^{-tmq}\prod _{i=1}^m\mathbb{E}\left[1-X_i+e^t{X}_i\right]\left(\forall x\in \left[0,1\right],e^{tx}\le 1-x+e^{t}x\right)$$ $$={\left[e^{-tq}\left(1-p+e^{t}p\right)\right]}^m.$$

现在，函数 $f:t\mapsto e^{-tq}\left(1-p+e^{t}p\right)=\left(1-p\right)e^{-tq}+p{e}^{t\left(1-q\right)}$ 在 $t=\log \frac{q\left(1-p\right)}{p\left(1-q\right)}$ 处达到最小值。将这个 $t$ 的值代入上述不等式中得到 $\mathbb{P}\left[\hat{p}\ge q\right]\le e^{-m\mathrm{D}\left(q\parallel p\right)}$ 。$\square$ 注意，对于任意 $ϵ>0,ϵ\le 1-p$ ，选择 $q=p+ϵ$ ，定理暗示

$$\mathbb{P}\left[\hat{p}\ge p+ϵ\right]\le e^{-m\mathrm{D}\left(p+ϵ\parallel p\right)}.\text{\hspace{1em}(D.6)}$$

这是一个比Hoeffding不等式(定理D.2)更精细的界限，因为根据Pinsker不等式(命题E.7)，$\mathrm{D}\left(p+ϵ\parallel p\right)\ge \frac{1}{2}{\left(2ϵ\right)}^2=2{ϵ}^2$ 。类似地，我们可以通过对随机变量 $Y_i=1-X_i$ 应用该定理来推导一个对称的界限。然后，对于任何 $ϵ>0,ϵ\le p$ ，在选择 $q=p-ϵ$ 的情况下，该定理暗示

$$\mathbb{P}\left[\hat{p}\le p-ϵ\right]\le e^{-m\mathrm{D}\left(p-ϵ\parallel p\right)}.\text{\hspace{1em}(D.7)}$$