漫谈概率论与信息论中的不等式

本文证明常用的概率或信息论相关的不等式，会持续更新~

k-$\sigma$ Rule

对于随机变量$X$，如果满足正态分布$N(\mu, \sigma^2)$，那么有

$\begin{aligned} \Pr(\mu -1\sigma \leq X\leq \mu +1\sigma )&\;\approx 68.27\%\\ \Pr(\mu -2\sigma \leq X\leq \mu +2\sigma )&\;\approx 95.45\%\\ \Pr(\mu -3\sigma \leq X\leq \mu +3\sigma )&\;\approx 99.73\% \end{aligned}$

它的证明使用累积分布函数即可，如对于$2\sigma$区间来说，

$\begin{align} \Pr(\mu -2\sigma \leq X\leq \mu +2\sigma ) &=\Pr( -2 \leq\frac{X- \mu}{\sigma } \leq 2) \\ &=\Phi (2)-\Phi (-2) \\ &\approx 0.9772-(1-0.9772) \\ &\approx 95.45\% \end{align}$

其中，

$\Phi (x)=\frac {1}{\sqrt {2\pi }}\int _{-\infty }^{x}e^{-t^{2}/2}\,dt$

这个不等式可以用于异常处理，例如数据服从正态分布，或者通过一定的处理后服从正态分布，那么数据的取值落到区间$[\mu - 3\sigma, \mu + 3\sigma]$外的概率为$1 - 99.73\%$，是极小概率，可以认为是异常值。

马尔可夫不等式

假设非负随机变量$X$有概率密度函数 $f(x)$定义在$\Omega$上，根据连续概率分布的均值定义，有，

$\begin{align} \mathbf{E}[x] &= \int_{\Omega}xf(x)dx \\ &= \int_{U}xf(x)dx + \int_{\Omega-U}xf(x)dx \\ &\geq \int_{U}xf(x)dx \\ &\geq \int_{U}\alpha f(x)dx \\ &= \alpha P(x \ge \alpha) \end{align}$

这里$U = [\alpha, \infty), \Omega=[0, \alpha)$有特例。

于是有，

$P(X \geqslant a) \leqslant \frac{\mathbf{E}[X]}{a}$

这是一个很强的定理，不需要假设 $f(x)$ 是具体的分布的概率密度函数。取$\mathbf{E}[X] = \mu, \alpha = 5\mu$，有

$P(X \ge 5\mu) \le \frac{1}{5}$

换成一个具体的语境来说是，不超过五分之一的人数收入超过平均水平的五倍。

不过马尔可夫不等式要求随机变量非负，这对于很多概率分布来说并不满足，如正态分布。那怎么办呢？一种技巧就是引入绝对值，这是一会提到的切比雪夫不等式的处理技巧，另外一种技巧是引入指数变换，因为指数变换总是非负的。以上要求$x \ge \alpha \gt 0$，那么任给$\lambda \gt 0$有，

$e^{\lambda x} \ge e^{\lambda \alpha} \gt 0$

代入到马尔可夫不等式中，有

$\begin{align} P(x \geqslant a) &= P(e^{\lambda x} \geqslant e^{\lambda a}) \newline &\le e^{-\lambda a} \mathbf{E}\left[e^{\lambda x} \right] \newline &= \min_{\lambda} e^{-\lambda a} \mathbf{E}\left[e^{\lambda x} \right] \end{align}$

最后一部分是因为理论上只要$\lambda \gt 0$即可，因此为了获得更高的近似估计精度，不等式右端应该取最小值。

马尔可夫不等式可以用来推导切比雪夫不等式。

切比雪夫不等式

对于随机变量$X$，有均值和方差分别为$\mu, \sigma^2$，切比雪夫不等式为，

$\operatorname{P}(|X-\mu| \geq k \sigma) \leq \frac{1}{k^{2}}$

另外一种相似的形式，

$P(| X - \mu| \ge \xi) \le \frac{\sigma^2}{\xi ^{2}}$

证明，

$\begin{aligned} \operatorname{P}(|X-\mu| \geq k \sigma) &=\mathrm{E}\left(I_{|X-\mu| \geq k \sigma}\right) \\ &=\mathrm{E}\left(I_{\left(\frac{x_{-\mu}}{k \sigma}\right)^{2} \geq 1}\right) \\ & \leq \mathrm{E}\left(\left(\frac{X-\mu}{k \sigma}\right)^{2}\right) \\ &=\frac{1}{k^{2}} \frac{\mathrm{E}\left((X-\mu)^{2}\right)}{\sigma^{2}} \\ &=\frac{1}{k^{2}} \end{aligned}$

这里$I$值指示函数。

如果只考虑单边情况，有更一般化的形式，称为Cantelli’s inequality，

$\displaystyle P(X-\mathbb {E} [X]\geq \lambda )= \begin{cases} \leq {\frac {\sigma ^{2}}{\sigma ^{2}+\lambda ^{2}}}&\;{\text{if }}\lambda >0,\\[8pt] \geq 1-{\frac {\sigma ^{2}}{\sigma ^{2}+\lambda ^{2}}}&\;{\text{if }}\lambda <0. \end{cases}$

Gibbs 不等式

Gibbs 不等式，

$D_{KL}(q(z)|p(z|x)) \ge 0$

容易证明，

$\begin{align} D_{KL}(q(z)|p(z|x)) &= \sum_{z\in \mathbb{Z}}q(z) \log{\frac{q(z)}{p(z|x)}} \newline &= -\sum_{z\in \mathbb{Z}}q(z) \log{\frac{p(z|x)}{q(z)}} \newline &\geqslant \log{\sum_{z\in \mathbb{Z}}q(z) \frac{p(z|x)}{q(z)}} \newline &=\log \sum_{z \in \mathbb{Z}} p(z|x) \newline &= 0 \end{align}$

这不就是 KL 散度大于等于 0 的证明！

Jensen 不等式

凸函数有一个直观的几何性质，即凸函数两点间的割线在该区间函数上方，可以用数学表示，

$tf(x_{1})+(1-t)f(x_{2})\geq f\left(tx_{1}+(1-t)x_{2}\right),0\leq t\leq 1$

这是实函数版本。其概率论版本如下，

$\varphi \left(E(X)\right)\leq E(\varphi (X))$

基于 Jensen 不等式还能导出很多有趣的不等式。EM算法的推导也涉及 Jensen 不等式。

Hoeffding 不等式

Hoeffding 不等式可以参考资料Hoeffding’s inequality。

$\begin{align} P(H(x)\neq f(x)) &= \sum_{i=0}^{[T/2]}\binom{T}{k}(1-\varepsilon)^{k}\varepsilon^{T-k} \\ &\leqslant \exp(-\frac{1}{2}T(1-2\varepsilon)^2) \end{align}$

负熵不等式

负熵不等式，

$\displaystyle \mathrm {H} (\lambda p_{1}+(1-\lambda )p_{2})\geq \lambda \mathrm {H} (p_{1})+(1-\lambda )\mathrm {H} (p_{2})$

考虑到熵$H(x)$的凹性，使用 Jensen 不等式容易证得。

大数定理

有 Weak law，

$\lim _{n \rightarrow \infty} \operatorname{P}\left(\left|\overline{X}_{n}-\mu\right|>\varepsilon\right)=0$

使用切比雪夫不等式易得，

$S_{n}=X_{1}+\dots+X_{n}$ $P\left(\left|\frac{S_{n}}{n}-\mu\right| \geqslant r\right) \leqslant \frac{\mathbf{V} \mathbf{a} \mathbf{r}\left[S_{n} / n\right]}{\varepsilon^{2}}$

另外，Strong law 如下，

$\operatorname{P}\left(\lim _{n \rightarrow \infty} \overline{X}_{n}=\mu\right)=1$