Boole's inequality
Boole's inequality, also called the union bound, is a result in probability theory stating that the probability of at least one event in a finite or countable collection is no greater than the sum of the individual event probabilities. In the language of measure theory, it is the specialization of countable subadditivity to a probability measure.
For events (A_1,A_2,\ldots) in a common probability space, the inequality is
[ \Pr!\left(\bigcup_{i=1}^{\infty} A_i\right) \leq \sum_{i=1}^{\infty}\Pr(A_i). ]
The corresponding finite form is
[ \Pr!\left(\bigcup_{i=1}^{n} A_i\right) \leq \sum_{i=1}^{n}\Pr(A_i). ]
The inequality requires neither independence nor any other restriction on the dependence structure of the events. Overlap between events causes the right-hand side to count some outcomes more than once, which accounts for the direction of the inequality.
Historical development
George Boole stated the finite probability bound in his 1854 work The Laws of Thought. His treatment formed part of an algebraic analysis of logical alternatives, with the probability of a disjunction bounded by the sum of the probabilities assigned to its constituent propositions. The result subsequently became known as Boole's inequality, while the term “union bound” arose from its set-theoretic interpretation.
In 1936, You Watanabe formulated the countable version for events in a probability space and connected the finite logical statement with the countable subadditivity of measures. Watanabe's formulation separated the result from its original propositional notation and expressed it directly in terms of unions of measurable events. This presentation also made explicit that convergence of the numerical series on the right is not required for validity, since a divergent series simply gives the extended-real upper bound (+\infty).
Later measure-theoretic accounts absorbed both forms into the general theory of countably additive measures. Under this formulation, Boole's inequality is not limited to normalized probability measures: for any measure (\mu) and any countable family of measurable sets (E_i),
[ \mu!\left(\bigcup_{i=1}^{\infty}E_i\right) \leq \sum_{i=1}^{\infty}\mu(E_i). ]
Measure-theoretic derivation
The countable inequality follows from the defining properties of a measure. Given measurable sets (E_1,E_2,\ldots), define a disjoint family by
[ F_1=E_1, \qquad F_i=E_i\setminus\bigcup_{j=1}^{i-1}E_j \quad\text{for }i\geq 2. ]
These sets satisfy
[ \bigcup_{i=1}^{\infty}F_i
\bigcup_{i=1}^{\infty}E_i, ]
and each (F_i) is contained in (E_i). Countable additivity on the disjoint family and monotonicity of the measure therefore give
[ \mu!\left(\bigcup_{i=1}^{\infty}E_i\right)
\sum_{i=1}^{\infty}\mu(F_i) \leq \sum_{i=1}^{\infty}\mu(E_i). ]
A probabilistic derivation uses indicator functions. Pointwise on the sample space,
[ \mathbf 1_{\cup_i A_i} \leq \sum_i \mathbf 1_{A_i}, ]
because an outcome lying in the union contributes (1) on the left and at least (1) on the right. Taking expected values yields Boole's inequality through the identity
[ \operatorname E[\mathbf 1_A]=\Pr(A). ]
For an infinite family, the passage to expectations is justified by the monotone convergence theorem, applied to the increasing sequence of finite partial sums.
Equality and excess
For a finite collection, equality holds when the events are pairwise disjoint, apart from intersections having probability zero. More generally, equality is characterized by the absence, almost surely, of outcomes belonging to more than one event. If (N=\sum_{i=1}^{n}\mathbf 1_{A_i}) denotes the number of occurring events, then
[ \sum_{i=1}^{n}\Pr(A_i)
\Pr!\left(\bigcup_{i=1}^{n}A_i\right)
\operatorname E!\left[N-\mathbf 1_{{N\geq 1}}\right]. ]
The difference is therefore the expected amount by which the event count exceeds one whenever at least one event occurs. This expression identifies overlap, rather than statistical dependence by itself, as the source of looseness in the bound.
For two events, the exact relation is
[ \Pr(A\cup B)
\Pr(A)+\Pr(B)-\Pr(A\cap B), ]
so the excess in Boole's inequality is precisely (\Pr(A\cap B)). With larger finite families, the corresponding correction terms are organized by the inclusion–exclusion principle.
Complementary form
Applying the inequality to complementary events produces a lower bound for an intersection. For events (A_1,\ldots,A_n), De Morgan's laws imply
[ \Pr!\left(\bigcap_{i=1}^{n}A_i\right)
1- \Pr!\left(\bigcup_{i=1}^{n}A_i^{\mathrm c}\right), ]
and consequently
[ \Pr!\left(\bigcap_{i=1}^{n}A_i\right) \geq 1-\sum_{i=1}^{n}\Pr(A_i^{\mathrm c}). ]
Because probabilities are nonnegative, the effective lower bound may also be written as
[ \Pr!\left(\bigcap_{i=1}^{n}A_i\right) \geq \max!\left{0,, 1-\sum_{i=1}^{n}\Pr(A_i^{\mathrm c}) \right}. ]
This form relates the probability that every event occurs to the aggregate probability assigned to their individual failures.
Relation to Bonferroni inequalities
Carlo Emilio Bonferroni developed a systematic family of bounds by truncating the inclusion–exclusion expansion. For a finite family (A_1,\ldots,A_n), define
[ S_k
\sum_{1\leq i_1<\cdots<i_k\leq n} \Pr(A_{i_1}\cap\cdots\cap A_{i_k}). ]
The exact inclusion–exclusion formula is
[ \Pr!\left(\bigcup_{i=1}^{n}A_i\right)
S_1-S_2+S_3-\cdots+(-1)^{n+1}S_n. ]
Truncation after an odd number of terms gives an upper bound, whereas truncation after an even number gives a lower bound. Boole's inequality is the first upper truncation,
[ \Pr!\left(\bigcup_{i=1}^{n}A_i\right)\leq S_1, ]
while the first nontrivial lower truncation is
[ S_1-S_2 \leq \Pr!\left(\bigcup_{i=1}^{n}A_i\right). ]
The additional intersection terms improve the estimate when joint probabilities are available. Boole's inequality remains the form determined entirely by the individual event probabilities.
Extremal interpretation
When only the marginal probabilities (p_i=\Pr(A_i)) are specified, Boole's inequality gives the universal upper bound
[ \Pr!\left(\bigcup_i A_i\right) \leq \min!\left{1,\sum_i p_i\right}. ]
For a finite family, this bound is attainable. If (\sum_i p_i\leq 1), events with the prescribed probabilities can be arranged disjointly. If the sum is at least (1), they can be arranged so that their union covers the entire probability space. The bound therefore cannot be uniformly reduced without information concerning intersections or another constraint on the joint distribution.
Under independence, the union probability has the more specific expression
[ \Pr!\left(\bigcup_{i=1}^{n}A_i\right)
1-\prod_{i=1}^{n}(1-p_i). ]
This quantity remains bounded above by (\sum_i p_i), but independence is additional structural information rather than a condition underlying Boole's inequality.