概率不等式

算法竞赛中有时会用到

随机化算法，这些算法的正确性与时空复杂度通常依赖于「某些随机事件发生的概率很小」这一前提。例如，快速排序的复杂度依赖于「所选的 pivot 元素几乎是最小或最大元素」这一事件较少发生。

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

Union Bound

记 为随机事件，则

即：一组事件中至少一个发生的概率，不超过每一个的发生概率之和。

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

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

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

Markov 不等式

设 是一个取值非负的随机变量，则对任意正实数 有

事实上，由于 Markov 不等式本身并没有用到随机变量除期望外的与分布有关的任何信息，因此直接应用这个不等式得到的约束通常很松。

证明

记 为事件 的示性函数，则有

进而

Chebyshev 不等式

设 是一随机变量，则对任意的 都有

特别地，当 取 时有

其中 是 的标准差。

证明

由已知，有

注意到 非负，故由 Markov 不等式可知

Chernoff 不等式

一般的 Chernoff 不等式可以从直接对随机变量 应用 Markov 不等式得出：

设 是一随机变量，则对任意的 都有

类似地，当 时有

Poisson 试验之和的 Chernoff 不等式

算法竞赛中涉及的随机变量通常没有那么「一般」，我们可以用概率论中的 Poisson 试验对其进行描述。

所谓 Poisson 试验，是指在只有两种可能结果的随机试验。

一次的 Poisson 试验的结果可以用一个取值为 或 的随机变量 进行刻画，其概率分布为

对于 Poisson 试验，我们有如下结论：

对于 个独立的 Poisson 试验 ，记 以及 ，则对任意 有

Hoeffding 不等式

若 为互相独立的实随机变量且 ，记随机变量 ，则

Chernoff 不等式和 Hoeffding 不等式都限制了随机变量偏离其期望值的程度。这两个不等式的证明过程较为冗长，有兴趣的同学可以查阅 Probability and Computing 一书中的相关章节。

从经验上讲，如果 不太接近 ，则该不等式给出的界往往相对比较紧；如果非常接近的话（例如在 UOJ #72 全新做法 中），给出的界则往往很松，此时更好的选择是使用 Chernoff 不等式。

应用举例

例：随机撒点估算圆周率

考虑下列估计圆周率 的精确值的算法：

在正方形区域 内随机生成 个点，记其中落入单位圆盘 的点数为 ，则可以取 为 的近似值。

问题：若要保证上述算法以至少 的概率返回相对误差不超过 的结果， 应该如何取定？

随机算法的正确性或复杂度经常依赖于某些“坏事件”不发生或很少发生。例如，快速排序的复杂度依赖于“所选的 pivot 元素几乎是最小或最大元素”这一坏事件较少发生。

本节介绍几个常用于分析“坏事件”发生概率的工具。

例：抽奖问题

一个箱子里有 个球，其中恰有 个球对应着大奖。你要进行若干次独立、等概率的随机抽取，每次抽完之后会把球放回箱子。请问抽多少次能保证以至少 的概率，满足 每一个 奖球都被抽到至少一次？

例：随机选取一半元素

给出一个算法，从 个元素中等概率随机选取一个大小为 的子集，保证 是偶数。你能使用的唯一的随机源是一枚均匀硬币，同时请你尽量减少抛硬币的次数（不要求最少）。

练习：Balls and Bins

个球独立随机地扔到 个盒子里，试证明：球最多的盒子中的球数以 的概率不少于 。