High-Dimensional Probability 第二章笔记-1

本章介绍几种集中不等式并介绍几种分布。笔记中只简单记录结论，证明过程可以参阅原书”High-Dimensional Probability An Introduction with Applications in Data Science”

2.1 为什么需要集中不等式

集中不等式量化了一个随机变量$X$相较于其均值$\mu$的偏移程度。这件事通常使用$X-\mu$分布两端的一个约束表示：

$$\mathbb P\{\left |X-\mu \right |>t\} \le something \, small$$

切比雪夫不等式就是一个较弱的集中不等式。

主张2.1.2：高斯分布的尾约束：令$g\sim N(0,1),$则对于所有的$t>0$，有：

$$(\frac{1}{t}-\frac{1}{t^3})\cdot\frac{1}{\sqrt{2\pi}}e^{-t^2/2}\le\mathbb P\{g\ge t\}\le\frac{1}{t}\cdot\frac{1}{\sqrt{2\pi}}e^{-t^2/2}$$

特别的，当$t>1$时，尾部由概率密度函数本身约束：

$$\mathbb{P}\{g\ge t\}\le\frac{1}{\sqrt{2\pi}}e^{-t^2/2}$$

2.1.2所展示的下界有可能是个负值，所以下界在t>1的时候才有意义。

使用大数定理可知当$N\to\infty$时$Z_N$趋向于正态分布。故独立同分布随机变量的和的界可以用高斯分布的尾约束来计算。但即使该约束的上界是以指数速度逼近0的，但$Z_N$和正态分布之间的误差可能会减小的过于缓慢。

定理2.1.3 Berry-Esseen中心极限定理： i.i.d.随机变量序列$X_i$及其和$S_N$，对于任意$N$和$t\in \mathbb R$，有：

$$\left|\mathbb P\{Z_N\ge t\}-\mathbb P\{g \ge t\}\right| \le \frac{\rho}{\sqrt{N}}$$

其中$\rho=\mathbb E|X_1-\mu|^3/\sigma^3\,,g\sim N(0,1)$
这个定理说明$Z_N$和正态分布的误差减小的过于缓慢，结合2.1.2使用会导致高斯分布尾约束的指数下降速率无法发挥作用

练习2.1.4：令$g\sim N(0,1)$。证明对于任意$t\ge 1$，有：

$$\mathbb{E} g^2 \mathbf{1}_{\{g>t\}}=t \cdot \frac{1}{\sqrt{2 \pi}} e^{-t^2 / 2}+\mathbb{P}\{g>t\} \leq\left(t+\frac{1}{t}\right) \frac{1}{\sqrt{2 \pi}} e^{-t^2 / 2}$$

2.2 霍夫丁不等式

定义 2.2.1 对称伯努利分布(Symmetric Bernoulli distribution)：一个随机变量$X$是对称伯努利分布（也叫拉德马赫分布）当且仅当它取值为-1或1的概率都为$1/2$，即：

$$\mathbb P(X=-1)=\mathbb P(X=1)=\frac{1}{2}$$

显然，如果$X$为一般(usual)伯努利分布当且仅当$2X-1$为对称伯努利分布。

定理2.2.2霍夫丁不等式：令$X_1,\dots,X_N$不相关的对称伯努利随机变量，$a=(a_1,\dots,a_N)\in \mathbb R^N$。对于任意$t\ge 0$，有：

$$\mathbb P\left\{\sum_{i=1}^Na_iX_i\right\}\le \exp\left(-\frac{t^2}{2||a||^2_2}\right)$$

霍夫丁定理可以看作是中心极限定理的集中形式。从中我们可以看出$\sum a_iX_i$的尾部和高斯分布的尾部表现相似。当$Z_n$和高斯分布之间的误差并不是指数级小的时候，我们可以依据该定理获得和高斯分布一样指数小的尾部约束。

评论2.2.4：值得注意的是，霍夫丁定理并不是渐进不等式，即它对所有的N都成立（其它经典的概率论定理可能只有在$n\to\infty$时才成立），而且N越大，霍夫丁不等式越强。这在实际应用中尤其是N和数据规模相关时尤其好用。

定理2.2.5双边霍夫丁不等式：令$X_1,\dots,X_N$不相关的对称伯努利随机变量，$a=(a_1,\dots,a_N)\in \mathbb R^N$。对于任意$t> 0$，有：

$$\mathbb{P}\left\{\left|\sum_{i=1}^N a_i X_i\right| \geq t\right\} \leq 2 \exp \left(-\frac{t^2}{2\|a\|_2^2}\right)$$

定理2.2.6只有一般约束的随机变量的霍夫丁不等式：令$X_1,\dots,X_N$不相关的随机变量，假设对于每个随机变量有$X_i\in[m_i,M_i]$，则对于任意的$t>0$，有：

$$\mathbb{P}\left\{\sum_{i=1}^N\left(X_i-\mathbb{E} X_i\right) \geq t\right\} \leq \exp \left(-\frac{2 t^2}{\sum_{i=1}^N\left(M_i-m_i\right)^2}\right)$$

练习2.2.8加强随机算法：有一个随机决策算法，该算法有$1/2+\delta$的概率返回正确答案，其中$\delta>0$。为了提升该算法，我们把该算法运行N次并进行投票（少数服从多数）。证明对于任意的$\epsilon\in(0,1)$，投票后算法正确率至少为$1-\epsilon$，只要：

$$N\ge\frac{1}{2\delta^2}ln(\frac{1}{\epsilon})$$

练习2.2.9均值的鲁棒估计：假设我们想估计随机变量$X$的均值$\mu$，从X独立采样出一批样本$X_1,\dots,X_N$。我们想要$\varepsilon$-准确度，即$\mu\in(\mu-\varepsilon,\mu+\varepsilon)$
(a) 证明采样数量为$N=O(\sigma^2/\epsilon^2)$的样本足以以3/4的概率达到$\varepsilon$-准确度，其中$\sigma^2$是X的方差
(b) 证明采样数量为$N=O(log(\delta^{-1})\sigma^2/\epsilon^2)$的样本足以至少以$1-\delta$的概率达到$\varepsilon$-准确度。

练习2.2.10小球概率：令$X_1,\dots,X_N$是非负的且连续分布的独立随机变量。假设$X_i$一致有界于1
(a) 证明$X_i$的矩生成函数满足：

$$\mathbb E(exp(-tX_i))\le\frac{1}{t}\quad for\,\,\,all\,\,\,t>0$$

(b) 推理对于任意的$\varepsilon >0$,有：

$$\mathbb P\left\{\sum_{i=1}^NX_i\le\varepsilon N\right\}\le(e\varepsilon)^N$$