The Union Bound and First Moment Method

The union bound says that the probability of at least one of several events happening is never more than the sum of their individual probabilities: $P(A_1 \cup A_2 \cup \dots \cup A_n) \le P(A_1) + P(A_2) + \dots + P(A_n)$. It costs nothing to derive — it's just double-counting overlaps in the wrong direction, which can only make the sum too big, never too small — but it is one of the most-used inequalities in probability because it requires no knowledge of how the events depend on each other. Suppose 100 independent signals each have a 1% chance of misfiring on a given day; the union bound says the chance that at least one misfires is at most $100 \times 0.01 = 1$, a bound so loose it says nothing here, but with 5 signals at 1% each it correctly caps the chance of any failure at 5%, which is often tight enough to be useful.

The first moment method goes further: if $X$ counts how many "bad" events occur and $E[X] < 1$, then $X$ must actually equal $0$ with positive probability — an average below one, for a count that can only be a whole number, forces some outcomes to be zero. This turns an expectation calculation, often the easiest quantity to compute, into a proof that a bad configuration can be avoided entirely. It is the workhorse behind existence proofs in combinatorics: to show a structure with a certain property exists, count the expected number of "flaws" under a random construction, and if that expectation is below one, a flawless instance must exist somewhere in the random construction's support.