正态分布有很多很好的理论性质，一种宽松些的考虑是sub-Gaussian的随机变量．
定义
定义：设\mathrm{x}为均值\mu的随机变量，那么\mathrm{x}（以及中心化的\mathrm{x}-\mu）被称为sub-Gaussian随机变量，如果满足：\mathrm{x}的矩生成函数(moment generating function)不超过N(\mu,\sigma^2)的矩生成函数，即
\mathbb E[\exp(t\mathrm{x})]\leqslant \exp\Big(\mu t+\frac12\sigma^2t^2\Big).
只需考虑零均值．一个零均值的随机变量的矩生成函数不超过N(0,\sigma^2)的——\mathbb{E}[\exp(t\mathrm{x})]\leqslant\exp(\frac12\sigma^2t^2)，那它就是sub-Gaussian的．
命题（尾部概率）：上述定义下，对正数t，存在常数c，使得
\mathbb P(|\mathrm{x}| \gt t)\leqslant c\, \mathbb P(|\mathrm{z}| \gt t),\quad \mathrm{z}\sim N(0,\tau^2).
也就是说中心化的sub-Gaussian的随机变量不会有比正态变量“更厚的尾部”．这个其实是等价刻画．
命题的证明：（点击展开/收起）
为了证明命题，需要对正态分布的尾部概率有比较好的估计．粗略地说，标准正态的尾部概率衰减速度为\frac1x\exp(-x^2/2)，是指数级衰减．
引理：令x \gt 0，\Phi(x),\phi(x)分别为标准正态的c.d.f和p.d.f，那么
\int _ x^{+\infty}t\phi(t)\, \mathrm{d}t=\phi(x).
这是因为，对t\mapsto\phi(t)求导，恰有\phi'(t)=-t\phi(t)．
引理：那么
\frac{x}{1+x^2}\phi(x) \lt \Phi(-x) \lt \frac1x\phi(x).
推导
右边是因为
\begin{aligned}
0& \lt \int _ x^{+\infty}\Phi(-t)\, \mathrm{d}t =t\Phi(-t)\big| _ x^{+\infty}-\int _ x^{+\infty}-t\phi(-t)\, \mathrm{d}t\\
&=-x\Phi(-x)+\phi(x).
\end{aligned}
继续推左边，对上式积分，得
\begin{aligned}
0& \lt \int _ x^{+\infty}[-t\Phi(-t)+\phi(t)]\, \mathrm{d}t=-\int _ x^{+\infty}\Phi(-t)\, \mathrm{d}\frac{t^2}2+\Phi(-x)\\
&=-\frac{t^2}{2}\Phi(-t)\Big| _ x^{+\infty}+\int _ x^{+\infty}\frac{t^2}{2}(-\phi(-t))\, \mathrm{d}t+\Phi(-x)\\
&=\frac{x^2}{2}\Phi(-x)-\int _ x^{+\infty}\frac{t^2}{2}\phi(t)\, \mathrm{d}t+\Phi(-x)\\
&=\Big(1+\frac{x^2}{2}\Big)\Phi(-x)+\frac12\int _ x^{+\infty}t\phi'(t)\, \mathrm{d}t\\
&=\Big(1+\frac{x^2}{2}\Big)\Phi(-x)-\frac12x\phi(x)-\frac12\int _ x^{+\infty}\phi(t)\, \mathrm{d}t\\
&=\frac12[(1+x^2)\Phi(-x)-x\phi(x)].
\end{aligned}
回到前面的命题．利用Markov不等式，对任意\lambda \gt 0，
\mathbb{P}(\mathrm{x} \gt t)=\mathbb{P}(\exp(\lambda\mathrm{x}) \gt \exp(\lambda t))\leqslant \frac{\mathbb{E}(\exp(\lambda\mathrm{x}))}{\exp(\lambda t)}.
利用定义，
\begin{gathered}
\mathbb{P}(\mathrm{x} \gt t)\leqslant\exp\Big(\frac{1}2\sigma^2\lambda^2-t\lambda\Big),\quad \lambda \gt 0,\\
\mathbb{P}(\mathrm{x} \gt t)\leqslant\exp\Big({-\frac{t^2}{2\sigma^2}}\Big),\\
\mathbb{P}(|\mathrm{x}| \gt t)\leqslant2\exp\Big({-\frac{t^2}{2\sigma^2}}\Big).
\end{gathered}
右边是常数系数2，而前面求出的正态尾部的系数是\frac1t量级，因而我们考虑正态变量\mathrm{z}\sim N(0,\tau^2)，其中\tau^2 \gt \sigma^2．双边尾部
\begin{aligned}
&\mathbb{P}(|\mathrm{z}| \gt t)=2\, \mathbb{P}(\mathrm{z} \gt t)\\
\gt{}&\frac{2t/\tau}{1+t^2/\tau^2}\phi(t/\tau)=\frac{2t/\tau}{\sqrt{2\pi}(1+t^2/\tau^2)}\exp\Big({-\frac{t^2}{2\tau^2}}\Big).
\end{aligned}
对t分情况讨论．对小t，t\leqslant \tau，
\begin{gathered}
\mathbb{P}(|\mathrm{z}| \gt t)\geqslant\mathbb{P}(|\mathrm{z}| \gt \tau)=\phi(1)=\frac{1}{\sqrt{2\pi e}},\\
\mathbb{P}(|\mathrm{x}| \gt t)\leqslant 1\leqslant \sqrt{2\pi e}\, \mathbb{P}(|\mathrm{z}| \gt t).
\end{gathered}
对大t，t \gt \tau，现取\tau^2=2\sigma^2，则
\begin{aligned}
\frac{\mathbb{P}(|\mathrm{x}| \gt t)}{\mathbb{P}(|\mathrm{z}| \gt t)}& \lt \frac{\sqrt{2\pi}(1+t^2/\tau^2)}{t/\tau}\exp\Big({-\frac{t^2}{2}\Big(\frac{1}{\sigma^2}-\frac{1}{\tau^2}\Big)}\Big)\\
&=\sqrt{2\pi}\Big(\frac{t}{\tau}+\frac{\tau}{t}\Big)\exp\Big({-\frac{t^2}{2\tau^2}}\Big)\\
&\leqslant 2\sqrt{2\pi/\mathrm{e}}.
\end{aligned}
这就证明了，对sub-Gaussian的随机变量\mathrm{x}，取c=\sqrt{2\pi e}和\tau^2=2\sigma^2，有
\mathbb{P}(|\mathrm{x}| \gt t) \lt c\, \mathbb{P}(|\mathrm{z}| \lt t),\quad \mathrm{z}\sim N(0,\tau^2).
基本性质
在命题的证明里，我们证明了如下的结论：
定理：设\mathrm{x},\mathrm{z}分别是中心化的sub-Gaussian变量和正态变量，都是\sigma^2参数，那么
\begin{gathered}
\mathbb{P}(\mathrm{x} \gt t)\leqslant \exp\Big({-\frac{t^2}{2\sigma^2}}\Big),\\
\mathbb P(\mathrm{z} \gt t)\leqslant\frac{1}{t/\sigma}\phi(t/\sigma)=
{\frac{1}{\sqrt{2π}} } \frac{σ}{t}
\exp\Big( {- \frac{t^2}{2σ^2}} \Big).
\end{gathered}
也就是尾部概率都拥有指数衰减速度．
定理：Sub-Gaussian的中心化\mathrm{x}的方差满足\operatorname{Var}(\mathrm{x})\leqslant\sigma^2．
这是因为，由\mathbb{E}[\exp(t\mathrm{x})]\leqslant \exp(t^2\sigma^2/2)得
\begin{gathered}
1+t\, \mathbb{E}(\mathrm{x})+\frac{t^2}{2}\mathbb{E}(\mathrm{x}^2)+o(t^2)\leqslant 1+t^2\sigma^2/2+o(t^2),\\
\mathbb{E}(\mathrm{x}^2)\leqslant \sigma^2+o(1),\quad t\to0.
\end{gathered}
定理：若随机变量\mathrm{x}有界，即a\leqslant \mathrm{x}-\mathbb{E}(\mathrm{x})\leqslant b，那么\mathrm{x}是sub-Gaussian的．
由Hoeffding引理，\mathbb{E}[\exp(t(\mathrm{x}-\mathbb{E}\mathrm{x}))]\leqslant \exp(\frac12(\frac{b-a}{2})^2t^2)．
定理：Sub-Gaussian变量的数乘、相加，还是得到sub-Gaussian变量．
只考虑零均值的两个相加．由Hölder不等式，
\begin{aligned}
&\mathbb{E}[\exp(t(\mathrm{x}+\mathrm{y}))]=\mathbb{E}[\exp(t\mathrm{x})\exp(t\mathrm{y})]\\
\leqslant{}&\Big[\mathbb{E}\exp\Big(t\mathrm{x}\frac{\sigma+\tau}{\sigma}\Big)\Big]^{\sigma\mathbin/(\sigma+\tau)}\Big[\mathbb{E}\exp\Big(t\mathrm{y}\frac{\sigma+\tau}{\tau}\Big)\Big]^{\tau\mathbin/(\sigma+\tau)}\\
\leqslant{}&\Big[\exp\Big(\frac12t^2\frac{(\sigma+\tau)^2}{\sigma^2}\sigma^2\Big)\Big]^{\sigma\mathbin/(\sigma+\tau)}\Big[\exp\Big(\frac12t^2\frac{(\sigma+\tau)^2}{\tau^2}\tau^2\Big)\Big]^{\tau\mathbin/(\sigma+\tau)}\\
={}&\exp\Big(\frac12t^2(\sigma+\tau)^2\Big).
\end{aligned}
当考虑独立的变量时，结果更为简单——显然把参数当作标准差/方差来操作就行了．例如，考虑i.i.d的n个sub-Gaussian随机变量，那么有
命题：平均\frac1n\sum \mathrm{x} _ i是sub-Gaussian随机变量，方差参数是\sigma^2/n．由此，
\mathbb{P}\Big(\frac1n\sum \mathrm{x} _ i-\mathbb{E}\mathrm{x} \gt t\Big)\leqslant \exp\Big({-\frac{nt^2}{2\sigma^2}}\Big).
定理：设0\leqslant t \lt 1，那么对中心化的sub-Gaussian变量\mathrm{x}，其平方有
\mathbb{E}\exp\Big(\frac{t\mathrm{x}^2}{2\sigma^2}\Big)\leqslant\frac{1}{\sqrt{1-t}}.
证明这个定理．
只考虑0 \lt t \lt 1．
引理：
\int _ {-\infty}^{+\infty}\exp(-ax^2)\, \mathrm{d}x=\sqrt{\frac\pi a},\quad a \gt 0.
由正态分布经两次换元不难推出这个式子：
\begin{gathered}
\int _ {-\infty}^{+\infty}\exp(-x^2/2)\, \mathrm{d}x=\sqrt{2\pi},\\
\int _ {-\infty}^{+\infty}\exp(-x^2)\, \mathrm{d}x=\sqrt{\pi}.
\end{gathered}
回到定理．由\mathbb{E}\exp(\lambda\mathrm{x})\leqslant\exp(\lambda^2\sigma^2/2)，得
\mathbb{E}\exp\Big(\lambda\mathrm{x}-\frac{\lambda^2\sigma^2}{2t}\Big)\leqslant\exp\Big(\frac{\lambda^2\sigma^2}{2}\frac{t-1}{t}\Big),\quad \lambda\in\mathbb{R}.
接下来对两边求\lambda的积分．先来算右边，利用引理，结果为
\sqrt{\pi\frac{2t}{(1-t)\sigma^2}}=\frac{1}{\sigma}\sqrt{\frac{2\pi t}{1-t}}.
对于左边，考虑Fubini定理，先固定x求\lambda的积分．配方：
\begin{gathered}
\begin{aligned}
\lambda{x}-\frac{\lambda^2\sigma^2}{2t}&=-\frac{\sigma^2}{2t}\Big(\lambda-\frac{x}{\sigma^2/t}\Big)^2+\frac{\sigma^2}{2t}\frac{x^2}{\sigma^4/t^2}\\
&=-\frac{\sigma^2}{2t}\Big(\lambda-\frac{x}{\sigma^2/t}\Big)^2+\frac{tx^2}{2\sigma^2}.
\end{aligned}\\
\int _ {-\infty}^{+\infty}\exp\Big\{-\frac{\sigma^2}{2t}\Big(\lambda-\frac{x}{\sigma^2/t}\Big)^2+\frac{tx^2}{2\sigma^2}\Big\}\, \mathrm{d}\lambda\\
=\exp\Big(\frac{tx^2}{2\sigma^2}\Big)\sqrt{\frac{2\pi t}{\sigma^2}}.
\end{gathered}
就有
\begin{gathered}
\frac{\sqrt{2\pi t}}{\sigma}\, \mathbb{E}\exp\Big(\frac{t\mathrm x^2}{2\sigma^2}\Big)\leqslant \frac{1}{\sigma}\sqrt{\frac{2\pi t}{1-t}},\\
\mathbb{E}\exp\Big(\frac{t\mathrm x^2}{2\sigma^2}\Big)\leqslant\frac{1}{\sqrt{1-t}}.
\end{gathered}
Hoeffding不等式
令\mathrm{x} _ i\, (i=1,\dots,n)为独立的sub-Gaussian变量，方差参数是\sigma _ i^2，那么它们的中心化均值是方差参数为\sum\sigma _ i^2的sub-Gaussian变量．由此立得如下的Hoeffding不等式：
定理：令\mathrm{s}=\frac1n\sum \mathrm{x} _ i，而\mu=\frac1n\sum\mathbb{E}(\mathrm{x} _ i)，则
\mathbb{P}(\mathrm{s}-\mu \gt t)\leqslant\exp\Big({-\frac{n^2t^2}{2\sum\sigma^2 _ i}}\Big).
当\sigma _ i都相等，就回到了上面的命题，\mathrm{s}是方差参数\sigma^2/n的sub-Gaussian变量，单边尾部概率\exp(-nt^2/2\sigma^2)．
推论：如果还知道有界，a _ i\leqslant \mathrm{x} _ i\leqslant b _ i，那么\mathrm{s}就是方差参数为\sum(b _ i-a _ i)^2/4的sub-Gaussian变量，
\mathbb{P}(\mathrm{s}-\mu \gt t)\leqslant\exp\Big({-\frac{2n^2t^2}{\sum(b _ i-a _ i)^2}}\Big).
特别地，如果都有a\leqslant \mathrm{x} _ i\leqslant b，那么
\mathbb{P}(\mathrm{s}-\mu \gt t)\leqslant\exp\Big({-\frac{2nt^2}{(b-a)^2}}\Big).
Leave a Reply