并集界

形式陈述与证明 ​

对同一概率空间中的有限个事件 $A_1,\dots ,A_n$，

$$\text{Pr}\left(\bigcup _{i=1}^n{A}_i\right)\le \sum _{i=1}^n\text{Pr}(A_i).$$

事件不必独立。逐点比较指示函数即可看见原因：某个结果若落在并集中，左边的指示函数为 $1$，右边至少有一项为 $1$；若它不在并集中，两边都不产生正贡献。因此

$${\mathbf{1}}_{{\cup }_i{A}_i}\le \sum _i{\mathbf{1}}_{A_i},$$

两边取期望公理库期望Expectation · Expected value实值或复值随机变量关于概率测度的 Lebesgue 积分。便得结论。由概率测度的可数次可加性，同样证明也给出 $\text{Pr}({\cup }_{i\ge 1}{A}_i)\le \sum _{i\ge 1}\text{Pr}(A_i)$；这里索引必须可数。对任意不可数事件族，不能不经可测性论证便直接“求和”。

两个事件时，精确关系是容斥式

$$\text{Pr}(A\cup B)=\text{Pr}(A)+\text{Pr}(B)-\text{Pr}(A\cap B).$$

并集界只是舍去了非负的交集项。事件两两不交时等号成立；独立既非前提，也不保证等号。

把许多局部保证合成一个整体保证 ​

设有限假设类 $H$ 中每个 $h$ 都有坏事件 $B_h$，且 $\text{Pr}(B_h)\le 2e^{-2m{\epsilon }^2}$。那么

$$\text{Pr}(\mathrm{\exists }h\in H:B_h)\le 2|H|e^{-2m{\epsilon }^2}.$$

令右边不超过 $\delta$，便得到 $m\ge \log (2|H|/\delta )/(2{\epsilon }^2)$。这解释了为什么候选规则数通过 $\log |H|$ 进入有限假设类泛化界公理库有限假设类泛化界Finite-class generalization bound固定假设的集中加上对有限类并集，得到同时成立的风险偏差界。：指数尾概率抵消了线性的事件数量。

同一图像也出现在赌博机中。若希望 $K$ 个臂在 $T$ 个时刻的置信区间全部覆盖真实均值，可以把每个“臂—时刻”失败概率压到 $\delta /(KT)$，再对 $KT$ 个失败事件求并。这样得到的是一个同时成立的高概率事件，而非 $KT$ 个彼此割裂的边际陈述。

松弛的边界 ​

并集界只计数，不利用重叠。若 $A_1=\cdots =A_n=A$，真实并集概率是 $\text{Pr}(A)$，上界却是 $n\text{Pr}(A)$，甚至会超过 $1$；此时可再取 $min\{1,\sum _i\text{Pr}(A_i)\}$，但重叠信息仍被丢失。反过来，若事件很稀少且交集概率远小于单事件概率，并集界往往已经接近精确。

它与独立性公理库独立性Statistical independence若干 σ-代数的任意有限事件选择都按概率乘积分解的性质。的乘法规则解决不同问题：独立性帮助计算交集，并集界控制“至少一个失败”。需要更精细地利用局部依赖时，可转向容斥、Bonferroni 界或 Lovász 局部引理公理库Lovász 局部引理Lovász local lemma当坏事件概率小且依赖稀疏时，所有坏事件同时不发生的概率为正。，而不能把独立性硬塞进并集界的条件。

一个数值例子能校准“松但可用”。若 100 个候选各自失败概率至多 ${10}^{-4}$，无论相关结构如何，至少一个失败的概率至多 $0.01$。若这些事件互斥且各概率恰为 ${10}^{-4}$，界取等；若它们其实是同一个事件，真实概率只有 ${10}^{-4}$。并集界用放弃重叠信息换取不需要建模依赖的可靠性。

对随时间增长的事件族，失败预算应可求和。例如令第 $t$ 轮失败概率至多 $6\delta /({\pi }^2{t}^2)$，可数并集界与 $\sum _{t\ge 1}{t}^{-2}={\pi }^2/6$ 给出“所有时刻同时成功”的概率至少 $1-\delta$。若每轮都只给固定 $0.01$ 失败率，无穷求和发散，不能推出无限时域同时保证。

参考资料

• Patrick Billingsley, Probability and Measure, 3rd ed., Wiley, 1995, probability measures and subadditivity.
• Stéphane Boucheron, Gábor Lugosi, Pascal Massart, Concentration Inequalities, Oxford University Press, 2013, Ch. 2.