因为常常需要知道随机变量，以及他们的和偏离均值的情况，所以需要一系列集中不等式。

在集中不等式中有两种思路，一种是矩法，可以得到 $X \sim \mathcal{N}\left(\mu, \sigma^{2}\right)$ 包括Markov和Chebyshev不等式在内的各种估计：

$\mathbb{P}[|X-\mu| \geq t] \leq \frac{\mathbb{E}\left[|X-\mu|^{k}\right]}{t^{k}}$

另一种是Chernoff方法，也就是通过 $\mathbb{P}[(X-\mu) \geq t]=\mathbb{P}\left[e^{\lambda(X-\mu)} \geq e^{\lambda t}\right] \leq \frac{\mathbb{E}\left[e^{\lambda(X-\mu)}\right]}{e^{\lambda t}}$ 一步放缩，把问题转化成对M.G.F的估计。

（1）在M.G.F比较好估计的时候，用Chernoff 方法比较多。

（2）矩法看起来粗糙，但是用矩法（所有的k）能得到的最好的估计不会比Chernoff方法得到的差。

Hoeffding 不等式

第一类发展的不等式是Hoeffding 不等式，我们要把变量限制在次高斯分布上。

定义：一个随机变量 X ，有均值 $\mu=\mathbb{E}[X]$ ，而且存在 $\sigma$ 满足： $\mathbb{E}\left[e^{\lambda(X-\mu)}\right] \leq e^{\sigma^{2} \lambda^{2} / 2}$ 对于任意的实数 $\lambda$ 成立，就叫做一个次高斯分布。

例子： $X \sim \mathcal{N}\left(\mu, \sigma^{2}\right)$ 就是有参数 $\sigma$ 的次高斯分布

例子：X 有界而且 $X \in[a, b]$ ，那么 X 是次高斯分布而且有参数 $\frac{b-a}{2}$

例子：Rademacher 随机变量是次高斯分布，参数 $\sigma =1$

等价判别：次高斯分布有很多，也有很多不同的判别方法，以下等价

（1）存在 $\sigma$ 使得 $\mathbb{E}\left[e^{\lambda(X-\mu)}\right] \leq e^{\sigma^{2} \lambda^{2} / 2}$ 对于任意的实数 $\lambda$ 成立（根据Wiki，可以在e前面加上常数）

（2）存在一个常数 $c\geq 0$ 和一个高斯变量 $Z \sim \mathcal{N}\left(0, \tau^{2}\right)$ 使得 $\mathbb{P}[|X-\mu| \geq s] \leq c \mathbb{P}[|Z| \geq s] \quad \text { for all } s \geq 0$

（3）存在一个常数 $\theta \geq 0$ 使得 $\mathbb{E}\left[(X-\mu)^{2 k}\right] \leq \frac{(2 k) !}{2^{k} k !} \theta^{2 k} \quad \text { for all } k=1,2, \ldots .$

（4）存在一个常数 $\sigma \geq 0$ 使得 $\mathbb{E}\left[e^{\frac{\lambda (X-\mu)^{2}}{2 \sigma^{2}}}\right] \leq \frac{1}{\sqrt{1-\lambda} }$ 对于任意的 $\lambda \in[0,1)$

第一个判别是对M.G.F有限制，第二个判别是说这个分布的tail bound 被一个高斯分布bound住，第三个判别是对矩直接限制。

上面的四个判断都需要转化到zero-mean的分布上考虑，根据HDP上的论述，还有其他的一些判别手段，不需要转化成zero-mean：
（5）同样控制尾分布，但是（2）中是和一个具体的高斯尾分布比较，可以替换成一个高斯型尾分布:

$\mathbb{P}\{|X| \geq t\} \leq 2 \exp \left(-t^{2} / K_{}^{2}\right) \quad \text { for all } t \geq 0$ （根据Wiki，这里2换成别的一个C也可以）

（6）同样控制矩，不过（3）中只是对偶数矩控制，而且形式不好利用。可以替换成对Lp norm的控制：

$\|X\|_{L^{p}}=\left(\mathbb{E}|X|^{p}\right)^{1 / p} \leq K_{} \sqrt{p} \quad \text { for all } p \geq 1$ （这里p是整数或者是所有大于等于1的实数都可以）

（7）控制 $X^2$ 的M.G.F，不过不同于（4）：

$\mathbb{E} \exp \left(\lambda^{} X^{2}\right) \leq \exp \left(K_{}^{2} \lambda^{}\right) \quad \text { for all } \lambda \text { such that }0\leq\lambda \leq \frac{1}{K_{}^2}$

注意：这里有bound是正常的，假如对所有的正数 $\lambda$ 都成立这个式子，那么X就是有界随机变量。

（8）控制 $X^2$ 的M.G.F，不过只要在一点有界就好了：

$\mathbb{E} \exp \left(X^{2} / K_{}^{2}\right) \leq C，K>0$

※这些等价关系的证明很有用，告诉我们如何从随机变量的一个性质转化成为另外一种性质。

次高斯分布空间：

（1）中心次高斯分布，结合次高斯参数 $\sigma$ 作为norm，构成一个Banach空间。

如果是两个独立的 $X,Y$ ，有次高斯参数 $\sigma _1,\sigma _2$ ,他们的和的次高斯参数可以缩小到 $\sqrt{\sigma _1^2+\sigma _2^2}$

（2）全部的次高斯分布，结合 $|| . ||_{\psi_2}$ 范数，构成一个Banach空间。

$\left\|\sum_{i=1}^{N} X_{i}\right\|_{\psi_{2}}^{2} \leq C \sum_{i=1}^{N}\left\|X_{i}\right\|_{\psi_{2}}^{2}$ (要求独立）

次高斯分布的centering inequality：

关于L2 norm 有个中心化不等式： $\|X-\mathbb{E} X\|_{L^{2}} \leq\|X\|_{L^{2}}$

这样的不等式保证了我们在使用mean zero的不等式时候不得不把随机变量中心化是可行的。

关于 $\psi_2$ norm 也有这样的不等式 $\|X-\mathbb{E} X\|_{\psi_{2}} \leq C\|X\|_{\psi_{2}}$ ，核心的想法就是L1 norm 可以被 $\psi_2$ norm控制住。但是这里的C取不到1。

定理：一个次高斯分布会有尾概率估计：

$\mathbb{P}[|X-\mu| \geq t] \leq 2 e^{-\frac{t^{2}}{2 \sigma^{2}}}$ （左右各一半）

定理（Hoeffding）：假设随机变量 $X_{i}, i=1, \ldots, n$ 独立，有均值 $\mu_{i}$ 和次高斯系数 $\sigma _i$ ，设 $\mu=\Sigma\mu_i$ $\sigma ^2=\Sigma\sigma _i^2$ , $X=\Sigma X_i$ ,

$P(|X-\mu|\geq t)\leq2exp\{-\frac{t^2}{2\sigma^2} \}$

Khinthine 不等式

是Hoeffding 不等式的推广，对mean zero sub Gaussian r.v的linear combination 的Lp norm的上下界估计，大概会跟combination coefficient的l2 norm差不多大。

最直接的应用就是，这些mean zero sub Gaussian r.v是Rademacher r.v

定理： $X_{1}, \dots, X_{N}$ 是独立的次高斯分布，零均值单位方差，

在 $p\ge 2$ 的时候有 $\left(\sum_{i=1}^{N} a_{i}^{2}\right)^{1 / 2} \leq\left\|\sum_{i=1}^{N} a_{i} X_{i}\right\|_{L^{p}} \leq C K \sqrt{p}\left(\sum_{i=1}^{N} a_{i}^{2}\right)^{1 / 2}$

其中 $K=\max _{i}\left\|X_{i}\right\|_{\psi_{2}}$

在 $p=1$ 的时候 $c(K)\left(\sum_{i=1}^{N} a_{i}^{2}\right)^{1 / 2} \leq\left\|\sum_{i=1}^{N} a_{i} X_{i}\right\|_{L^{1}} \leq\left(\sum_{i=1}^{N} a_{i}^{2}\right)^{1 / 2}$

$p \in(0,2)$ 的时候应该是差不多

HDP p31有证明的概要。

Bernstein 不等式

为了得到更general的集中不等式，需要比次高斯更大的类别：

定义: X是一个随机变量而且有均值 $\mu=\mathbb{E}[X]$ ，如果存在非负的参数 $(\nu, \alpha)$ 使得：

$\mathbb{E}\left[e^{\lambda(X-\mu)}\right] \leq e^{\frac{\nu^{2} \lambda^{2}}{2}} \quad \text { for all }|\lambda|<\frac{1}{\alpha}$ 那么称作一个次指数分布

很显然，次指数分布考虑了M.G.F不能再每个点展开的情况，所以比次高斯更广泛。

例子：标准高斯的平方是一个次指数分布

等价判别：

如果一个随机变量满足以下之一，就是一个次指数分布

（1） $\mathbb{E}\left[e^{\lambda (X-\mu)}\right] \leq e^{\frac{v^{2} \lambda^{2}}{2}} \quad \text { for all }|\lambda|<\frac{1}{\alpha}$

（2） $\mathbb{E}\left[e^{\lambda (X-\mu)}\right]<\infty \text { for all }|\lambda| \leq c_{0}$

（3） $\mathbb{P}[|X-\mu| \geq t] \leq c_{1} e^{-c_{2} t} \quad \text { for all } t>0$

（4） $\gamma:=\sup _{k\ge2}\left[\frac{\mathbb{E}\left[(X-\mu)^{k}\right]}{k !}\right]^{1 / k}$ 是有限的

第一条是对M.G.F局部做限制，第二条是说假如M.G.F在原点局部能展开，那么一定是次指数，第三条对尾分布做限制，被指数分布控制着，第四条是对矩直接做限制。

HDP中提供了以下的一些判别：

（5） $\mathbb{P}[|X| \geq t] \leq c_{1} e^{-c_{2} t} \quad \text { for all } t>0$

（6） $\|X\|_{L^{p}}=\left(\mathbb{E}|X|^{p}\right)^{1 / p} \leq K_{} p \quad \text { for all } p \geq 1$

（7） $\mathbb{E} \exp (\lambda|X|) \leq \exp \left(K_{} \lambda\right) \quad \text { for all } \lambda \text { such that } 0 \leq \lambda \leq \frac{1}{K_{}}$

对绝对值X的M.G.F做限制

（8） $\mathbb{E} \exp \left(|X| / K_{}\right) \leq 2$ 一点有界

和SubGaussian的联系：

$\left\|X^{2}\right\|_{\psi_{1}}=\|X\|_{\psi_{2}}^{2}$

$\|X Y\|_{\psi_{1}} \leq\|X\|_{\psi_{2}}\|Y\|_{\psi_{2}}$

次指数同样有centering 不等式

定理：

一个次指数分布会有尾概率估计

$\mathbb{P}[|X-\mu |\geq t] \leq\left\{\begin{array}{ll}{2e^{-\frac{t^{2}}{2 v^{2}}}} & {\text { if } 0 \leq t \leq \frac{v^{2}}{\alpha}} \\{2e^{-\frac{t}{2 \alpha}}} & {\text { for } t>\frac{v^{2}}{\alpha}}\end{array}\right.$

定理：假设随机变量 $X_{i}, i=1, \ldots, n$ 独立，有均值 $\mu _i$ ,次指数系数 $(v_k,\alpha_k)$

设 $\mu=\Sigma\mu_i$

$\alpha_{*}:=\max _{k=1, \ldots, n} \alpha_{k}$

$v_{*}:=\sqrt{\sum_{k=1}^{n} v_{k}^{2}}$

那么 $\mathbb{P}\left[|X-\mu|\geq t\right] \leq\left\{\begin{array}{ll}{2e^{-\frac{ t^{2}}{2\left(v_{*}^{2}\right)}}} & {\text { for } 0 \leq t \leq \frac{v_{*}^{2}}{ \alpha_{*}}} \\{2e^{-\frac{ t}{2 \alpha_{*}}}} & {\text { for } t>\frac{v_{*}^{2}}{ \alpha_{*}}}\end{array}\right.$

一个用于量化中心极限定理的版本：

$\mathbb{P}\left\{\left|\frac{1}{\sqrt{N}} \sum_{i=1}^{N} X_{i}\right| \geq t\right\} \leq\left\{\begin{array}{ll}{2 \exp \left(-c t^{2}\right),} & {t \leq C \sqrt{N}} \\{2 \exp (-ct \sqrt{N}),} & {t \geq C \sqrt{N}}\end{array}\right.$

所以在比 $C \sqrt{N}$ 小的时候是有常数方差的高斯分布

很多时候直接对M.G.F bound有难度，考虑bound 矩：

Bernstein condition： $| \mathbb{E}\left[(X-\mu)^{k}\right] | \leq \frac{1}{2} k ! \sigma^{2} b^{k-2} \quad \text { for } k=2,3,4, \ldots$

例子：有界随机变量且 $|X-\mu| \leq b$ 都符合，包括下面的Bernstein-type inequality最主要也是对这种有界随机变量使用。

定理：有Bernstein condition的随机变量有M.G.F的估计：

$\mathbb{E}\left[e^{\lambda(X-\mu)}\right] \leq 1+\frac{\lambda^{2} \sigma^{2} / 2}{1-b|\lambda|} \leq e^{\frac{\lambda^{2} \sigma^{2} / 2}{1-b|\lambda |}}$ $|\lambda|<\frac{1}{b}$

所以他一定是次指数分布，有系数 $(\sqrt{2} \sigma, 2 b)$

$X_{1}, X_{2}, \cdots X_{n}$ 是独立的随机变量，每个 $X_i$ 满足Bernstein condition $(\sigma_i,b)$

$X=X_{1}+\cdots+X_{n}, \quad \mu=E\left[X_{1}\right]+\cdots+E\left[X_{n}\right]$

$\sigma^{2}=\sigma_{1}^{2}+\cdots+\sigma_{n}^{2}$

现对于 $\frac{1}{b}>\lambda \geqslant 0$ 有：

$\begin{aligned}P(X-\mu \geqslant t) &=P\left(e^{\lambda(X-\mu)} \geqslant e^{\lambda t}\right) \\&=e^{-\lambda t} \prod_{i=1}^{n} E e^{\lambda\left(x_{i}-\mu_{i}\right)} \\&=e^{-\lambda t} e^{\frac{\lambda^{2} \sigma^{2} / 2}{1-b \lambda}}\end{aligned}$

取 $\lambda=\frac{t}{b t+\sigma^{2}} \in\left[0, \frac{1}{b}\right)$ 就可以得到

$\mathbb{P}[|X-\mu| \geq t] \leq 2 e^{-\frac{t^{2}}{2\left(\sigma^{2}+bt\right)}}$ （对负的一边做了类似的处理）

注意：（1）这里Bernstein type的exp中是 $\frac{t^{2}}{2\left(\sigma^{2}+b t\right)}$ ，在t很小的时候也是接近Gaussian分布的，但是和Hoeffding 不同的是这边那是 $\sigma$ ，真实方差，那边是b，区间长度。我们知道 $\sigma$ 更小，所以Bernstein在小 t 问题上会更好一些。

（2）而且统计中很多问题会要用到方差。

（3）有界随机变量除了可以直接用Hoeffding ，Bernstein，还可以用Bennett不等式。Bennett不等式揭示了在小偏差是高斯型，大偏差是Poisson型，可能更精确一点。

Concentration 不等式（一）

Concentration 不等式（一）

Hoeffding 不等式

Khinthine 不等式

Bernstein 不等式

推荐阅读更多精彩内容