概率不等式

算法竞赛中有时会用到随机化算法，这些算法的正确性与时空复杂度通常依赖于「某些随机事件发生的概率很小」这一前提。

例如，快速排序的复杂度依赖于「所选的 pivot 元素几乎是最小或最大元素」这一事件较少发生。

本文将简要介绍一些用于分析随机化算法的工具并给出几个简单应用的例子。

Union bound

记 \(A_1,\cdots,A_m\) 为随机事件，则 \[ \mathrm{Pr}\left(\bigcup_{i=1}^m A_i\right) \leq \sum_{i=1}^m \mathrm{Pr}(A_i) \] 即：一组事件中至少一个发生的概率，不超过每一个的发生概率之和。

实际上，这一结论还可以稍作加强：

一组事件中至少一者发生的概率，不小于 每一个的发生概率之和，减掉每两个同时发生的概率之和。
一组事件中至少一者发生的概率，不超过 每一个的发生概率之和，减掉每两个同时发生的概率之和，加上每三个同时发生的概率之和。
……

随着层数越来越多，交替出现的上界和下界也越来越紧。这一系列结论形式上类似容斥原理，证明过程也和容斥类似，这里略去。

Markov 不等式

设 \(X\) 是一个取值非负的随机变量，则对任意正实数 \(a\) 有 \[ \mathrm{Pr}(X \ge a) \le \frac{\mathrm{E}(X)}{a} \] 由于 Markov 不等式本身并没有用到随机变量除期望外的与分布有关的任何信息，因此直接应用这个不等式得到的约束通常很松。

证明：

记 \(\mathrm{I}\) 为事件 \(X \ge a\) 的示性函数，则 \[ \mathrm{I} \le \frac{X}{a} \] 进而 \[ \mathrm{Pr}(X \ge a) =\mathrm{E\cdot I} \le \mathrm{E}\left(\frac{X}{a}\right) = \frac{\mathrm{E}(X)}{a} \]

Chebyshev 不等式

设 \(X\) 是一随机变量，则对任意的 \(a > 0\) 有 \[ \mathrm{Pr}\left(|X-\mathrm{E}(X)| \ge a\right) \le \frac{\mathrm{Var}(X)}{a^2} \] 特别地，当 \(a\) 取 \(k\sigma\) 时有（ \(\sigma\) 是 \(X\) 的标准差） \[ \mathrm{Pr}\left(|X-\mathrm{E}(X)| \ge k\sigma\right) \le \frac{1}{k^2} \] 证明：

由已知，有 \[ \mathrm{Pr}\left(|X-\mathrm{E}(X)| \ge a\right) = \mathrm{Pr}\left(\left(X-\mathrm{E}(X)\right)^2 \ge a^2\right) \] 注意到 \((X-\mathrm{E}(X))^2\) 非负，故由 Markov 不等式可知 \[ \mathrm{Pr}\left(\left(X-\mathrm{E}(X)\right)^2 \ge a^2\right) \le \frac{\mathrm{E}(X-\mathrm{E}(X))^2}{a^2} = \frac{\mathrm{Var}(X)}{a^2} \]

Chernoff 不等式

一般的 Chernoff 不等式可以从直接对随机变量 \(\mathrm{e}^{tX}\) 应用 Markov 不等式得出：

设 \(X\) 是一随机变量，则对任意的 \(t > 0\) 都有 \[ \mathrm{Pr}(X \geq a)=\mathrm{Pr}\left(\mathrm{e}^{t X}>\mathrm{e}^{t a}\right) \leq \frac{\mathrm{E}( \mathrm{e}^{t X})}{\mathrm{e}^{t a}} \] 类似地，当 \(t < 0\) 时有 \[ \mathrm{Pr}(X \le a)=\mathrm{Pr}\left(\mathrm{e}^{t X}>\mathrm{e}^{t a}\right) \leq \frac{\mathrm{E}( \mathrm{e}^{t X})}{\mathrm{e}^{t a}} \]

Poisson 试验之和的 Chernoff 不等式

这一段先咕咕咕。

Hoeffding 不等式

若 \(X_1,\cdots,X_n\) 为互相独立的实随机变量且 \(X_i \in [a_i,b_i]\) ，记随机变量 \(X = \sum_{i=1}^nX_i\) ，则 \[ \mathrm{Pr}(|X-\mathrm{E}(X)| \geq \epsilon) \leq 2 \exp \left(\frac{-2 \epsilon^2}{\sum_{i=1}^n\left(b_i-a_i\right)^2}\right) \] Chernoff 不等式和 Hoeffding 不等式都限制了随机变量偏离其期望值的程度。

这两个不等式的证明过程较为冗长，有兴趣的同学可以查阅 Probability and Computing 一书中的相关章节。

从经验上讲，如果 \(\mathrm{E}(X)\) 不太接近 \(a_1 + \cdots + a_n\) ，则该不等式给出的界往往相对比较紧；

如果非常接近的话（UOJ72），给出的界往往很松，此时更好的选择是使用 Chernoff 不等式