内容提要
介绍了集中不等式的概念，引入了 Chernoff 界方法，并以此证明了 Hoeffding 不等式。
什么是集中不等式？
Concentration inequalities，中文译作「集中不等式」，是概率论中的一类不等式，描述了一个随机变量的取值是否集中在某个特定的值附近，换句话说，相对于这个特定值偏离了多少，从概率上讲这个偏离的可能性又如何量化。这个特定的值通常取的是总体均值。数学上，这类不等式的形式可写作
$$ \mathbb{P}\{|X-\mu|>t\} \leq \text{something small} $$这个不等式表明了，我们希望随机变量 $X$ 以很高的概率围绕在其均值附近波动。最简单、也最为我们熟悉的集中不等式当属 Chebyshev 不等式：如果 $X$ 的均值是 $\mu$，方差是 $\sigma^2$，那么
$$ \mathbb{P}\{|X-\mu|>t\} \leq \frac{\sigma^2}{t^2} $$这个不等式当然是很一般的──我们只要求方差有限，除此之外并没有对 $X$ 的分布做更多要求。但是，在很多应用场景中，它还是太弱了，弱在不等式右边的东西不够小，或者更具体地说，当 $t\to\infty$ 时收敛到 0 的速度不够快。我们希望能有指数级别的收敛。
从渐进的观点看，当样本量足够大时，我们可以使用中心极限定理近似地得到样本均值偏离总体均值的概率，而正态分布的尾概率是指数衰减的。
Proposition 1.
若 $Z\sim\mathcal{N}(0,1)$，则对任意 $t>0$，都有
$$ \biggl(\frac1t-\frac{1}{t^3}\biggr)\cdot\frac{1}{\sqrt{2\pi}}e^{-t^2/2} \leq \mathbb{P}\{Z\geq t\} \leq \frac{1}{t}\cdot\frac{1}{\sqrt{2\pi}}e^{-t^2/2} $$对于上界，有
$$ \begin{align*} \mathbb{P}\{Z\geq t\} &= \frac{1}{\sqrt{2\pi}}\int_t^\infty e^{-x^2/2}\,dx \\ &\leq \frac{1}{\sqrt{2\pi}}\int_t^\infty \frac{x}{t}e^{-x^2/2}\,dx \\ &= \frac{1}{t\sqrt{2\pi}} \int_t^\infty -\frac{\partial}{\partial x}e^{-x^2/2}\,dx \\ &= \frac{1}{t}\cdot\frac{1}{\sqrt{2\pi}}e^{-t^2/2} \end{align*} $$对于下界，利用等式
$$ \int_t^\infty (1-3x^{-4})e^{-x^2/2}\,dx = \biggl(\frac1t-\frac1{t^3}\biggr)e^{-t^2/2} $$不过，我们还需考虑到渐进误差的存在，也就是说，用正态分布的尾概率去近似样本均值的尾概率不是一种严格的做法。事实上，渐进误差并不必然是指数衰减的，因此我们必须从非渐进的角度入手，而集中不等式正是这样的角色。
Note
Berry-Esseen 定理 表明，中心极限定理中概率分布的收敛速率至少是 $O(1/\sqrt{n})$，不必然是指数级别的收敛。
Chernoff 界方法
在开始介绍一系列集中不等式之前，我们先讲一个很具有普适性的方法：Chernoff bound，它被广泛用于各种集中不等式的证明。
利用 Markov 不等式，对 $s>0$, 我们有
$$ \mathbb{P}\{X\geq t\} = \mathbb{P}\{e^{sX}\geq e^{st}\} \leq \frac{\mathbb{E}(e^{sX})}{e^{st}} $$不等式右边的 $m_X(s) := \mathbb{E}(e^{sX})$ 即随机变量的矩生成函数 (moment generating function, MGF)。更使我们喜闻乐见的是，分母是一个指数函数。这意味着，只要我们能控制 MGF 不要增长的太快，我们就能保证指数级收敛。
后文的各种集中不等式反复展示了这一技巧。
Hoeffding 不等式
首先介绍一个分布：对称 Bernoulli 分布，也叫 Rademacher 分布。如果随机变量 $X$ 均以 1/2 概率取值 –1 和 1，则称它服从对称 Bernoulli 分布。显然，$Z$ 服从（普通的）Berinoulli 分布当且仅当 $2Z-1$ 服从对称 Bernoulli 分布。
Hoeffding 不等式即是关于对称 Bernoulli 随机变量的。
Theorem 2 (Hoeffding’s Inequality).
设 $X_1,\dots,X_n$ 是独立的对称 Bernoulli 随机变量序列，$\bm{a}=(a_1,\dots,a_n)\in\mathbb{R}^n$ 是实值常向量。对任意 $t\geq0$，都有
$$ \mathbb{P}\Biggl\{\sum_{i=1}^n a_iX_i\geq t\Biggr\} \leq \exp\biggl(-\frac{t^2}{2\|\bm{a}\|_2^2}\biggr) $$不失一般性，设 $\|\bm{a}\|_2 = 1$。利用 Chernoff 界方法，对 $s>0$ 有
$$ \begin{align*} \mathbb{P}\Biggl\{\sum_{i=1}^n a_iX_i\geq t\Biggr\} &= \mathbb{P}\Biggl\{\exp\Biggl(s\sum_{i=1}^n a_iX_i\Biggr)\geq \exp(st)\Biggr\} \\ &\leq e^{-st}\mathbb{E}\Biggl[\exp\Biggl(\sum_{i=1}^n a_iX_i\Biggr)\Biggr] \\ &= e^{-st}\prod_{i=1}^n\mathbb{E}[\exp(sa_iX_i)] \end{align*} $$最后一个等式使用了独立性。计算 $\mathbb{E}[\exp(sa_iX_i)]$：
$$ \mathbb{E}[\exp(sa_iX_i)] = \frac12[\exp(sa_i)+\exp(-sa_i)] = \cosh(sa_i) \leq \exp(s^2a_i^2/2) $$其中的不等号来自：$\cosh(x)\leq\exp(x^2/2)$ 对 $x\in\mathbb{R}$ 成立，可通过 Taylor 展开证明。于是，我们得到
$$ \begin{align*} \mathbb{P}\Biggl\{\sum_{i=1}^n a_iX_i\geq t\Biggr\} &\leq e^{-st}\prod_{i=1}^n\mathbb{E}[\exp(sa_iX_i)] \\ &\leq e^{-st}\prod_{i=1}^n \exp(s^2a_i^2/2) \\ &= \exp\Biggl(-st+\frac{s^2}{2}\sum_{i=1}^na_i\Biggr) \\ &= \exp\biggl(-st+\frac{s^2}{2}\biggr) \end{align*} $$最后一个等式利用了 $\sum_ia_i^2=1$。现在，选择最优的 $s$ 让右边的值最小，显然，这个最优的 $s=t$，这样就得到了想要的结果。
我们可以轻松加愉快地得到双边版本的 Hoeffding 不等式：
Corollary 3 (Hoeffding’s Inequality, two-sided).
设 $X_1,\dots,X_n$ 是独立的对称 Bernoulli 随机变量序列，$\bm{a}=(a_1,\dots,a_n)\in\mathbb{R}^n$ 是实值常向量。对任意 $t\geq0$，都有
$$ \mathbb{P}\Biggl\{\left|\sum_{i=1}^n a_iX_i\right|\geq t\Biggr\} \leq 2\exp\biggl(-\frac{t^2}{2\|\bm{a}\|_2^2}\biggr) $$更一般地，对有界随机变量，我们也有 Hoeffding 不等式：
Theorem 4 (Hoeffding’s Inequality for Bounded Random Variables).
设 $X_1,\dots,X_n$ 是独立的随机变量序列，$\mathbb{E}(X_i) = \mu_i$ 且 $X_i\in[a_i,b_i]$。则对任意 $t\geq0$，都有
$$ \mathbb{P}\Biggl\{\sum_{i=1}^n (X_i-\mu_i)\geq t\Biggr\} \leq \exp\biggl(-\frac{2t^2}{\sum_{i=1}^n(b_i-a_i)^2}\biggr) $$不失一般性，设 $\mu_i=0$，即所有 $X_i$ 均值为 0，这也同时意味着 $a_i\leq0\leq b_i$。
我们首先证明 Hoeffding 引理，它是说，如果有界随机变量 $X\in[a,b]$ 且均值为 0，则对 $s\in\mathbb{R}$ 恒有
$$ \mathbb{E}(e^{sX}) \leq \exp\biggl(\frac{s^2(b-a)^2}{8}\biggr) $$因 $e^{sx}$ 是关于 $x$ 的凸函数，故对任意 $x\in[a,b]$，我们有
$$ e^{sx} \leq \frac{b-x}{b-a}e^{sa} + \frac{x-a}{b-a}e^{sb} $$将 $x$ 替换为 $X$，并两边取期望，注意我们已经假设 $X$ 均值为 0，因此
$$ \begin{align*} \mathbb{E}(e^{sX}) &\leq \frac{b-\mathbb{E}(X)}{b-a}e^{sa} + \frac{\mathbb{E}(X)-a}{b-a}e^{sb} \\ &= \frac{b}{b-a}e^{sa} + \frac{-a}{b-a}e^{sb} \end{align*} $$现在，我们需要证明
$$ \frac{b}{b-a}e^{sa} + \frac{-a}{b-a}e^{sb} \leq \exp\biggl(\frac{s^2(b-a)^2}{8}\biggr) $$不妨进行换元 $h = s(b-a)$，上式便等价于
$$ \exp\biggl(\frac{ha}{b-a}\biggr)\biggl(\frac{b}{b-a}+\frac{-a}{b-a}e^h\biggr) \leq \exp\biggl(\frac{h^2}{8}\biggr) $$取对数，我们需证明
$$ f(h) := \frac{ha}{b-a} + \log\biggl(\frac{b-e^ha}{b-a}\biggr) \leq \frac{h^2}{8} $$将 $f(h)$ 在 $h=0$ 处 Taylor 展开：
$$ f(h) = f(0) + f'(0)h + \frac12f''(\xi)h^2 \quad\text{for some $\xi$ between 0 and $h$} $$注意到 $f(0) = f^\prime(0) = 0$，而对 $\xi\in\mathbb{R}$ 我们恒有
$$ f''(\xi) = -\frac{e^\xi ab}{(b-e^\xi a)^2} \leq \frac14 $$这里我们使用了均值不等式得到 $-e^\xi ab \leq \frac14(-e^\xi a+b)^2$。这就证明了 $f(h)\leq\frac18h^2$，进而证明了 Hoeffding 引理。
回到定理的证明。仍然利用 Chernoff 界方法：
$$ \begin{align*} \mathbb{P}\Biggl\{\sum_{i=1}^n X_i\geq t\Biggr\} &= \mathbb{P}\Biggl\{\exp\Biggl(s\sum_{i=1}^n X_i\Biggr)\geq \exp(st)\Biggr\} \\ &\leq e^{-st}\mathbb{E}\Biggl[\exp\Biggl(\sum_{i=1}^n X_i\Biggr)\Biggr] \\ &= e^{-st}\prod_{i=1}^n\mathbb{E}[\exp(sX_i)] \\ &\leq e^{-st}\prod_{i=1}^n\exp\biggl(\frac{s^2(b_i-a_i)^2}{8}\biggr) \\ &= \exp\biggl(-st+\frac{s^2\sum_{i=1}^n(b_i-a_i)^2}{8}\biggr) \\ &\leq \exp\biggl(-\frac{2t^2}{\sum_{i=1}^n(b_i-a_i)^2}\biggr) \end{align*} $$倒数第三行调用了 Hoeffding 引理，最后一行通过取 $s=4t/\sum_{i=1}^n(b_i-a_i)^2$ 得到。
（未完待续～）
参考
- Wikipedia. “Concentration inequality.”
- Rigollet, Philippe, and Jan-Christian Hütter. 2023. “High-Dimensional Statistics.” arXiv preprint. arXiv:2310.19244.
- Vershynin, Roman. 2018. High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge University Press.
最后修改于 2024-09-04