Boole's inequality ($\mathbb{P}({\bigcup }_i{A}_i)\le \min \{1,{\sum }_i\mathbb{P}(A_i)\}$)

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,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,\dots ,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.

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,Taking expected values and using linearity of expectation proves the finite bound.^[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).

For three events in one classical probability space, the inclusion $A\setminus C\subset (A\setminus B)\cup (B\setminus C)$ and the union bound prove the displayed inequality. It is therefore an unconditional theorem of classical probability. In a polarization Bell test, a model assigning simultaneous setting-independent pass/fail outcomes to three possible analyzer directions must obey it. Equal unbiased marginals and quantum pair correlations instead give $P(A\setminus B)=\frac{1}{2}{\sin }^2({\theta }_A-{\theta }_B)$. Directions $0,\gamma ,2\gamma$ violate the resulting constraint for $0<\gamma <\pi /4$, because $2{\sin }^2\gamma <{\sin }^{2}2\gamma$. The conclusion excludes that common classical joint model. Conditional probabilities from sequential measurements cannot be inserted without their marginal factors or treated as if all three contexts shared an already established joint distribution.

For finitely many events, or a countable family with finite sum of individual probabilities, equality in the uncapped union bound holds exactly when every pairwise intersection has probability zero. Equivalently, at most one event occurs almost surely. Pairwise disjoint events give equality, but literal disjointness is stronger than necessary: shared outcomes of probability zero do not change either side. For the capped bound, if the sum exceeds one, equality instead means that the union is an almost sure event; overlap can then have positive probability.

The cap and the disjoint case are both sharp. If the individual probabilities sum to at most one, put the events on separate pieces of a sample space to attain their sum. The twelve-outcome disjoint example does this with two events of probability $1/3$. If the sum exceeds one, a covering union can attain the cap: on the same twelve-outcome sample space, $A=\{1,\dots ,8\}$ and $B=\{5,\dots ,12\}$ have sum $4/3$ and exact union probability one. These are sharpness examples, not an assertion that every overlapping family attains the bound. Positive-probability disjoint events are also not independent events, because their joint probability is zero while the product of their individual probabilities is positive.

For a finite family, the random variable $N={\sum }_i{1}_{A_i}$ counts the events that occur. Linearity of expectation gives $\mathbb{E}N={\sum }_i\mathbb{P}(A_i)$, while $\mathbb{P}(N\ge 1)$ is the exact union probability. Their difference isAn outcome in exactly $k\ge 1$ events contributes $k-1$ extra counts, weighted by its probability. This nonnegative difference vanishes exactly in equality in Boole's inequality. For two events it is $\mathbb{P}(A\cap B)$, as the inclusion-exclusion principle for probabilities shows. For more events, the Bonferroni inequalities use pairwise and higher intersection information to bound the exact union probability; blindly subtracting pairwise intersections from the sum gives a lower bound, rather than a corrected upper bound.

Severe overlap can make the union bound arbitrarily pessimistic. Let all $m$ events be the same event $A$ with probability $1/m$, where $m\ge 1$ is an integer. A concrete model is the discrete uniform distribution on $\{1,\dots ,m\}$ with $A=\{1\}$. The exact union probability is $1/m$, whereas the sum and capped bound are both one. The ratio is $m$: adding more names for the same event does not create more ways to fail. The identity above describes the gap in the uncapped sum; capping at one can reduce that gap.

A failure-probability budget assigns nonnegative numbers ${\delta }_i$ to a finite or countable family of failure events $F_i$ in a common probability space, with verified bounds $\mathbb{P}(F_i)\le {\delta }_i$. The union bound guarantees that the probability of any failure is at most $\min \{1,{\sum }_i{\delta }_i\}$. By De Morgan's laws and the complement rule of probability, the probability that every requirement succeeds obeysThus ${\sum }_i{\delta }_i\le \delta$ guarantees simultaneous success with probability at least $1-\delta$, even when all failure events depend on the same observations. The numbers ${\delta }_i$ are upper allowances; adding them is not a calculation of the exact failure probability.

For three requirements, give each a failure-probability budget ${\delta }_i=1/20$. The total budget is $3/20$, so simultaneous success has probability at least $17/20$. On a sample space of twenty equally likely outcomes, let $F_1=\{1\}$, $F_2=\{2\}$, and $F_3=\{3\}$. These disjoint events attain the budget and the success bound. If instead all three failure events equal $\{1\}$, their individual probabilities are unchanged, but exact failure has probability $1/20$ and simultaneous success has probability $19/20$. This second model shows how overlap can leave the guarantee conservative.

For $n$ requirements, an equal allocation ${\delta }_i=\delta /n$ is convenient; unequal allocations also work when some requirements are harder to satisfy. For infinitely many requirements indexed by $i\ge 1$, the allocation ${\delta }_i=\delta /2^i$ uses total budget $\delta$ by the geometric series. A fixed positive allowance for every requirement instead gives an infinite sum and no positive simultaneous-success guarantee from the union bound. The individual probability bounds must cover all the failure events being combined: omitting possible failure modes leaves the resulting guarantee about the listed requirements only. The same addition of error allowances underlies the Bonferroni correction in simultaneous hypothesis tests.

For $n\ge 2$, the intersection of all pairwise intersections $A_i\cap A_j$ is ${\bigcap }_i{A}_i$. Apply the union bound to the complements of the pairwise intersections and then take the complement to obtain the displayed lower bound. A sum exceeding $\left(\genfrac{}{}{0ex}{}{n}{2}\right)-1$ therefore forces positive common probability without any independence assumption.