引子

为什么要关注高维概率呢? 一个很有意思的现象是对于高维正态分布 , 有 的现象, 或者说, 大部分数据集中在一个半径为 的球壳上. 这在一维正态中表现为 原则. 我们先考虑一维随机变量.

高维概率讨论的核心之一是 concentration, 这有下面几种理解方式:

• 随机变量聚集的情况, 比如正态分布的 原则
• 分布的尾部的上界以及上界随着尾部的"缩小"上界收敛的速度
• 随机变量 是如何偏离它的均值 的

考虑一个例子: 独立重复地掷一枚均匀硬币, 正面得 分, 反面得 分(这是一个对称伯努利分布), 为掷 次后得得分, 求 , 或者求其上界.

很容易想到两种方式: 一是由 Chebyshev 不等式 , 此时 另一种方式是借助中心极限定理, 有 , 则

这是因为对于 以及任意 , 有 特别地, 对于 , 有

那么实际上是 在 时成立, 虽然这是指数收敛的, 但这是个渐进的结果. 事实上由 Berry-Esseen Theorem:

Berry-Esseen CLT. 设 是独立同分布的随机变量且均值均为 , 方差均为 , , 则对任意 有 其中 且 .

那么若由中心极限定理得到一个非渐进的结果, 就变成 , 这甚至劣于 .

是否存在非渐进且指数收敛的结果呢? Hoeffding 不等式将会给出这个结果.

Hoeffding's Inequality: sub-Gaussian

定理 1 设 i.i.d. 对称伯努利分布 , 则 PROOF 考虑利用矩母函数, 这是由 以及 . Q.E.D.

这有如下推论(记 ):

1: . (独立同分布对称伯努利分布的线性组合)

2: . (双侧概率)

3: 若 仅为有界随机变量且 , 则 上面的 Hoeffding 不等式给出了有界随机变量尾部的形如 的上界, 我们会称某个随机变量或者某个分布具有 Hoeffding 形式的不等式. 那自然就想问对于无界随机变量是否有这样的结果呢?

一个最容易想到的无界随机变量是 , 幸运的是, 由前文提到的 , 正态分布是具有 Hoeffding 形式的不等式的, 以正态分布为桥梁, 如果某些分布的尾巴比正态分布还要小, 那么它们肯定也具有 Hoeffding 形式的不等式, 这引出了一族分布称作 sub-Gaussian distribution, 更具体地, 可以通过下述条件来确定某个分布是否为 sub-Gaussian 或者说某个随机变量 是否服从 :

1: 尾部满足, 对任意 ,

2: 的矩满足 , , 其中 .

3: 的矩母函数满足 , .

4: 的矩母函数在某一点是有界的, 即 . 这里出现的常数 没有特殊含义, 可以被替换为任意大于 的常数.

5: 的矩母函数满足 , 若 .

其中 都是常数.

然后我们可以定义次高斯模 . 在全体 sub-Gaussian 随机变量的空间中满足范数的定义.

用次高斯模可以重写上述条件, 或者说上述 都和 有关, 如下:

1. 对任意 ;
2. 对任意 ;
3. ;
4. 若 , 则 对任意 .

下面是一些常见分布的次高斯模:

• ,
• ,
• 对于任意有界随机变量 , , 其中 .

首先给出广义 Hoeffding 不等式, 这不要求 同 sub-Gaussian. 同样也有线性组合的版本: 其中 .

Bernstein's inequality: sub-exp

次高斯分布已经足够庞大, 但是仍然漏掉了常见的一些分布, 比如泊松分布和指数分布都不是次高斯的, 这些分布的 tail 比次高斯分布更 "重" (这里的意思是密度函数的值更大). 比如设 是一个高斯分布, 但我们清楚 服从自由度为 1 的 分布 (更一般地, 服从正态分布的一系列随机变量的二次型都是服从 分布的), 将 和 的密度函数做比较, 可以明显发现在 的密度函数在 的上方.

考察 的尾部, 有 显然 严格成立, 因此没有办法使用 Hoeffding 不等式来研究 的 concentration. 同时注意到 的密度函数为 , 因此我们将重点放在至少具有指数 () 尾分布衰减的一类分布上, 并探究它们与 Hoeffding 不等式类似的结论与性质. 我们首先定义此指数性质.

命题 1 对于随机变量 , 下述结论是等价的, 其中出现的常数 之间至多差常数倍:

1. 的尾部满足对所有 都有 ;
2. 的矩满足对所有 都有 ;
3. 的矩母函数满足对所有 都有 ;
4. 的矩母函数在某点有界, 即 ;
5. 若 , 则 的矩母函数满足对所有 都有 .

我们略去这里的证明.

上面的定义和次高斯分布随机变量满足的性质极其相似, 我们将满足命题 1 诸性质的随机变量称为次指数随机变量, 并类比次高斯模 定义次指数模 次高斯分布和次指数分布具有紧密的联系, 首先任何次高斯分布都是次指数分布, 我们可以逐个验证上述每一条性质, 比如对于 , 这显然满足次指数分布的性质. 进一步地, 我们不加证明地给出下面的一些关于 和 的引理.

引理 1 当且仅当 , 且 .

引理 2 两个次指数随机变量的乘积是次指数的, 且

该引理的证明需要借助 Young 不等式: 若 且 且 , 那么 . 的这个关系称为共轭.

定义过 , 命题 1 的常数 也可以用 来替代, 如下

• , 其中
• , 其中 且 .

接下来我们给出 Bernstein 不等式.

定理 1 设 是独立的 均值的次指数随机变量, 则对任意的 , 均有

其中 是一个绝对常数.

Bernstein 不等式是在说, 在 比较小时上界是 的形式, 更像是一个正态分布, 有比较小的尾部; 在 比较大的时候上界是 的形式, 尾部的偏差增大.

很容易给出下面的两个推论.

1: 的线性组合 : 其中 .

2: 当 有上界 时, Bernstein 不等式的结果可加强, 即对任意的 , 有 其中 是 的方差.

Chernoff Bound: Poisson-like Bound

其中 , , i.i.d.

The Degree Bound of Random Graph

这是 Chernoff bound 的一些应用, 可以利用 Chernoff bound 和 union bound 来证明关于随机图 的下述结论, 记 是 的平均度数.

1: (Dense graph is regular graph.) 若 , 那么对任意 , 成立 w.h.p..

2: (Upper bound of degree of sparse graph.) 若 , 则对任意 , 成立 w.h.p.; 若 , 则对任意 , 成立 w.h.p.

3: (Lower bound of degree of sparse graph.) 若 , 则存在 , 成立 w.h.p.; 若 , 则存在 , 成立 w.h.p.

小结

这部分内容的核心其实就是独立随机变量和的 concentration.