我们继续讨论关于集中不等式的相关问题. 在前一篇文章中我们已经介绍了基本的集中不等式(Markov，Chebyshev等等)以及在其它一些更加复杂的集中不等式：Bernstein，Efron-Stein不等式等等. 本文将从次高斯(sub-Gaussian),次指数(sub-Exponential)分布的情形入手，来说明这些指数衰减不等式是如何得到的.

实际上从Markov，Chebyshev不等式中，我们已经得到了启发：随机变量的一阶矩和二阶矩可以帮助我们控制住偏差的概率. 这两个不等式适用的随机变量非常广泛，几乎只需要这两阶矩收敛。由此，如果把需要控制的随机变量的范围变小，我们是否就可能得到更强的不等式呢？能否实现指数级别的衰减呢？

事实上这是可以做到的. 从Markov不等式出发，有一个非常简洁的想法. \[ P(X>t)=P(e^{sX}>e^{st})\leq \frac{\mathbb{E}e^{sX}}{e^{st}} \] 注意到\(\mathbb{E}e^{sX}\)实际上就是\(X\)的矩母函数(Moment Generating Function). 如果我们能对矩母函数进行控制，就可以对右端项进行控制！

例如我们知道，标准正态分布的矩母函数\(\Phi(s)=\exp\{\frac{s^2}{2}\}\)，于是右端项就可以更近一步地计算为\(\exp\{\frac{s^2}{2}-st\}\). 由于原来的不等式对所有的\(s\)都成立，我们就可以选取一个比较好的\(s\)，使得右端项是最小的！由二次函数的知识，只要选\(s=t\)即可得到最小值\(\exp\{-\frac{t^2}{2}\}\).于是对于标准正态分布我们就得到 \[ P(X>t)\leq \exp\{-\frac{t^2}{2}\} \] 观察这个界，最为重要的事情就是当\(t\rightarrow \infty\)时，右边的上界是按照指数下降，并最终趋于零的. 而当\(t\)比较小的时候，这个上界也不会像Markov或者Chebyshev给出的界一样趋向于正无穷. 从这个意义上讲，我们认为这个界比Markov或者Chebyshev的界要强，并且在实际问题中也会有用的多.

当然我们也可以对非标准的正态分布\(N(\mu,\sigma^2)\)按照一样的方法，计算得到 \[ P(X-\mu>t)\leq \frac{\mathbb{E}e^{s(X-\mu)}}{e^{st}}=\exp\{\frac{\sigma^2s^2}{2}-st\} \] 同样求出右端项的最小值以后，可以得到一个\(\exp\{-\frac{\sigma^2t^2}{2}\}\)的上界.

同理我们也可以对\(P(X-\mut)\leq 2\exp\{-\frac{\sigma^2t^2}{2}\} \] 这一套对指数用Markov不等式的技术，称之为Chernoff Bound. 回顾得到这个指数衰减的界的过程，我们发现在这里最重要的事情就是对随机变量的矩母函数进行控制. 由此我们定义：一个均值为零的随机变量\(X\)叫做参数为\(\sigma\)的次高斯分布，如果其矩母函数满足 \[ \mathbb{E}e^{sX}\leq \frac{\sigma^2s^2}{2},\quad \forall s\in\mathbb{R} \] 从前面的推导可以看出，所有的次高斯分布的随机变量，都会满足和上面正态分布一样的概率上界.

接下来的问题就是，哪些随机变量是次高斯分布的？除了正态分布本身以外，一个非常重要的例子就是所有的有界随机变量. 这个定理叫做Hoeffding引理：如果随机变量\(X\in[a,b],\mathbb{E}X=0\)，那么\(X\)服从参数为\((b-a)^2/4\)的次高斯分布.

这是因为根据指数函数的凸性可以得到， \[ \mathbb{E}e^{sX}\leq \frac{-a}{b-a}e^{sa}+\frac{b}{b-a}e^{sb} \] 通过微积分的手段可以证明右端的上界是\(\exp\{s^2(b-a)^2/4\}\)

由此，我们就可以得到Hoeffding不等式: 对于独立有界的随机变量\(X_1,\cdots,X_n,X_i\in[a_i,b_i]\)，那么其均值\(\overline{X}=\frac{1}{n}\sum_{i=1}^nX_i\)满足 \[ \begin{align} P(\overline{X}-\mathbb{E}\overline{X}>t)&\leq \inf_{s}e^{-snt}\prod_{i=1}^n\mathbb{E}[e^{s(X_i-\mathbb{E}X_i)}]\\ &\leq \inf_s \exp\{-snt+\sum_{i=1}^n\frac{s^2(b_i-a_i)^2}{4}\}\\ &=\exp\{-\frac{2n^2t^2}{\sum_i(b_i-a_i)^2}\} \end{align} \] 次高斯分布有一个非常简单的性质：假设两个独立的随机变量\(X_1,X_2\)都是次高斯分布的，分别服从参数\(\sigma_1,\sigma_2\)，那么\(X_1+X_2\)就是服从参数为\(\sqrt{\sigma_1^2+\sigma_2^2}\)的次高斯分布. 这个结果的证明直接利用定义即可.

显然，不是所有常见的随机变量都是次高斯的. 例如指数分布就不是. 对于服从参数为\(\lambda\)的指数分布，其矩母函数 \[ \mathbb{E}e^{sX}=\int_0^\infty e^{sx}\lambda e^{-\lambda x}\mathrm{d}x =\frac{\lambda}{\lambda - s},\quad \forall s\lambda\)时，其矩母函数是不收敛的！因此次高斯分布的一系列结论对于指数分布都是不适用的. 我们可以把次高斯分布的随机变量类进行扩大，得到所谓的次指数分布. 对于非负的随机变量\(X\)，我们就把 \[ \mathbb{E}e^{sX}\leq \frac{a}{a-s},\quad\forall s\in(0,a) \] 成立的随机变量叫做次指数分布. 但正如前面次高斯分布的情形，我们更关心一些零均值随机变量的情形. 对于参数为\(\lambda\)的指数分布， 我们转而考察 \[ \begin{align} \mathbb{E}e^{\lambda(X-\frac{1}{\lambda})}=\exp\{-\frac{s}{\lambda}\}\frac{1}{1-(s/\lambda)} \end{align} \] 令\(f(t)=-t-\log(1-t)\),则通过微积分可以证明\(f(t)\leq t^2/(1-t)\). 从而我们也可以通过这样的方法来定义次指数分布：存在\((\sigma^2,b)\)使得对任意的\(s\in [0,1/b)\)都有 \[ \mathbb{E}e^{s(X-\mathbb{E}X)}\leq \exp\{\frac{s^2\sigma^2}{2}\},\quad\forall |s|