= Boole's inequality
{c}
{title2=$\mathbb P(\bigcup_i A_i)\leq\min\{1,\sum_i\mathbb P(A_i)\}$}
{wiki}
= Union bound
{synonym}
<Boole's inequality>, also called the <union bound>, bounds the <probability> that at least one of several <events> occurs by adding their individual <probabilities>. For a finite or <countable> family of <events> $A_i$ in the same <probability space>,
$$
\mathbb P\left(\bigcup_i A_i\right)\leq\min\left\{1,\sum_i\mathbb P(A_i)\right\}.
$$
The <union> includes outcomes where several <events> occur together. There is no <independence> assumption: adding the individual <probabilities> counts such outcomes repeatedly, which can only make the sum larger. The cap at one uses the total mass of a <probability measure>. For infinitely many <events>, the sum is a nonnegative <series>, possibly infinite; an infinite sum gives only the bound one. This is <countable subadditivity of a measure> specialized to a <probability measure>. See <Probability: Theory and Examples (fifth edition) by Rick Durrett> (Section 1.1, Theorem 1.1.1(ii), printed p. 2).
For example, choose uniformly from the twelve outcomes $\Omega=\{1,\ldots,12\}$, using the <discrete uniform distribution>. Put $A=\{1,2,3,4\}$. If $B=\{5,6,7,8\}$, these are <disjoint events> and their <union> has <probability> $8/12=2/3$, exactly the <union bound>. If $B=\{3,4,5,6\}$, the <union> has only six outcomes, so its exact <probability> is $1/2$, although both individual <probabilities> are still $1/3$ and the bound is still $2/3$. If $B=A$, the exact <probability> falls to $1/3$ with the same bound. These examples isolate <overlap in the union bound> by keeping the individual <probabilities> fixed.
\Image[/union-bound-finite-events-overlap.png]
{title=The same individual <event> <probabilities> give different exact <union> <probabilities> as overlap increases}
{description=Each panel is a fully specified <discrete uniform distribution> on twelve numbered outcomes. Blue means $A$ only, orange means $B$ only, purple means their <intersection>, and white means neither. The bottom bars compare the exact <union> <probability> with the sum of the individual <probabilities>. The three <unions> contain eight, six, and four outcomes; the sum counts eight in every panel.}
The <union bound> is useful when each <event> is easy to control but their joint behavior is difficult to determine. A short proof uses <indicator functions>: at every outcome,
$$
\mathbf 1_{\bigcup_{i=1}^n A_i}\leq\sum_{i=1}^n\mathbf 1_{A_i}.
$$
Taking <expected values> and using <linearity of expectation> proves the finite bound.<Introduction to Probability, Statistics, and Random Processes by Hossein Pishro-Nik/6.2.1 The Union Bound and Extension>{ref} For a <countable> family, the finite <unions> increase to the full <union>; <continuity of probability> passes the finite inequalities to the limit. The closure of a <sigma-algebra> under <countable unions> ensures that this limiting <union> is an <event>. For the <continuity of probability> step, see <Probability: Theory and Examples (fifth edition) by Rick Durrett> (Section 1.1, Theorem 1.1.1(iii), printed p. 2).
Back to article page
