集中不等式(2)：次高斯、次指数分布

我们继续讨论关于集中不等式的相关问题. 在前一篇文章中我们已经介绍了基本的集中不等式(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-\mu<-t)\)进行控制，并通过概率测度的次可加性(Union Bound)，得到 \[ P(|X-\mu|>t)\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 \] 而当\(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|<\frac{1}{b} \] 这里我们限制了\(s\)是一个非负数，是因为在\(\lambda<0\)的情形下，我们是无法通过Markov不等式得到指数衰减的概率控制的. 常见的次指数分布包括: 指数分布，Gamma分布，以及任何的有界随机变量. 对于次指数分布\((\sigma^2,b)\)，我们有以下的概率控制 \[ P(X\geq \mathbb{E}X + t) \leq \begin{cases} e^{-\frac{t^2}{2\sigma^2}} &0\leq t\leq \frac{\sigma^2}{b} \\ e^{-\frac{t}{2b}}& t>\frac{\sigma^2}{b} \end{cases} \] 这一结果的证明和次高斯分布是一样的套路. 只是在讨论右端项二次函数的最值的时候更复杂一些.

和次高斯分布一样，次指数分布也对加法是保持的. 具体来说，如果\(X_1,X_2\)分别是服从\((\sigma_1^2,b_1),(\sigma_2^2,b_2)\)的次指数分布，那么\(X_1+X_2\)是服从\((\sigma_1^2+\sigma_2^2,\max(b_1,b_2))\)

利用次高斯分布，次指数分布的尾端控制，我们实际上可以得到一些更有趣的结果. 这些结果经常出现在高维统计的问题中.

一些例子

有界随机变量的进一步讨论

假设\(X_1,\cdots,X_n\) 都是有界随机变量，且存在一个\(b\)使得\(|X-\mathbb{E}X|\leq b\)成立，\(X_i\)的方差是\(\sigma_i\). 从次高斯分布的讨论中，我们已经说明了这里的\(X_i\)是服从次高斯分布(参数为\(\frac{b^2}{2}\))的，并由此我们得到了Hoeffding不等式 \[ P(\overline{X}_n-\mathbb{E}\overline{X}_n\geq t)\leq \exp\{-\frac{nt^2}{2b^2}\} \] 当方差很小的时候，我们是否可以利用这一信息将右边的结果再加强一些呢？让我们回到对有界随机变量的生成函数的讨论. 实际上如果我们不利用指数函数的凸性，而是把它直接做Tylor展开，那么有 \[ \begin{align} \mathbb{E}e^{s(X-\mathbb{E}X)}&= 1+ \mathbb{E}(X-\mathbb{E}X)+\frac{s^2}{2}\mathbb{E}(X-\mathbb{E}X)^2+\sum_{k=3}^\infty\frac{s^k\mathbb{E}(X-\mathbb{E}X)^k}{k!}\\ &\leq 1+\frac{s^2\sigma^2}{2}+\sum_{k=3}^{\infty}\frac{s^k\sigma^2b^{k-2}}{k!}\\ &\leq 1+\frac{s^2\sigma^2}{2}+\frac{s^2\sigma^2}{2}\sum_{k=3}^\infty(|s|b)^{k-2}\\ &\leq 1+\frac{s^2\sigma^2}{2}\frac{1}{1-|s|b}\\ &\leq \exp\bigg\{\frac{\lambda^2\sigma^2}{2[1-|s|b]}\bigg\} \end{align} \] 首先当\(|s|<1/2b\)时上式右端项小于\(\exp(\lambda^2\sigma^2)\),这表明这一类随机变量是服从参数为\((2\sigma^2,2b)\)的次指数分布的.

其次利用这个结果和Chernoff界的一般技巧，我们就可以得到Bernstein不等式 \[ P(X\geq \mu+t) \leq \exp\bigg\{-\frac{t^2}{2[\sigma^2+bt]}\bigg\} \] 以及 \[ P(\overline{X}\geq \mathbb{E}\overline{X}_n+t) \leq \exp\bigg\{-\frac{t^2}{2[n^{-1}\sum_{i=1}^n\sigma_i^2+bt]}\bigg\} \] 于是当方差比较小, \(t\)也比较小的时候，我们就得到了比Hoeffding不等式更加紧的界.

\(\chi^2\)分布和高维几何.

假设\(Z\)是标准正态分布，那么\(Z^2\)是自由度为1的\(\chi^2\)分布. 计算其矩母函数得 \[ \mathbb{E}[\exp\{\lambda(Z^2-1)\}]=\frac{e^{-\lambda}}{\sqrt{1-2\lambda}}\leq e^{2\lambda^2},\quad \forall \lambda < \frac{1}{4} \] 这说明自由度为1的\(\chi^2\)分布是参数为\((2,4)\)的次指数分布. 进一步由次指数分布的加法性质，知道\(\chi_n^2\)分布是参数为\((2\sqrt{n},4)\)的次指数分布. 从而利用次指数分布的结论，我们有 \[ P(|\frac{1}{n}\chi_n^2-1|\geq t)\leq 2e^{-nt^2/8},\text{i.e.}, P(|\sum_{i=1}^nZ_i^2-n|\leq \varepsilon n)\leq 2e^{-(\varepsilon n)^2/8} \] 这一结果实际上是高维情况下一个非常神奇的现象. 这告诉我们标准的\(n\)维正态分布，随着\(n\)不断变大，这些点主要都分布在一个半径是\(\sqrt{n}\)的高维球面附近. 这一现象直接导致了一个更加深刻的结果: Johnson-Lindenstrauss引理！我们将在之后的文章中详细介绍.