Concept
The finite union bound as an existence argument
Let A_1,...,A_t be bad events in a finite uniform sample space Omega. Counting the union counts each bad outcome once; summing |A_i| counts it at least once and possibly repeatedly. Hence Pr(at least one bad event)<=sum_i Pr(A_i). The bad events need NOT be independent. If this sum is less than one, fewer than |Omega| outcomes are bad, so at least one outcome avoids every bad event. This proves existence. A deterministic algorithm can enumerate the finite outcomes and check the conditions until it finds one; the probability proof alone does not make that search efficient.
0
1
Updated 2026-11-07
Tags
Math