Consider 2 finite sets, \( A \) and \(B\). To calculate the number of items in both sets, we can calculate this by noticing that given that the items in the intersection belong to both A and B then if we add the items in A to the items in B we have double counted the numbers in the intersection so we just need to subtract it.
The diagram shows the (unique) elements in each set represented by blue dots, e.g. there are 7 elements in \( A \) as it contains 7 blue dots.
\begin{align}
|A \cup B| = |A| + |B| – |A \cap B|
\end{align}
To see this notice that if an element only belongs to \( A \) then it appears only once in the LHS and RHS, similarly for an element which only belongs to B. If an element belongs to \( A \cap B \) then it appears once in the LHS and for the RHS it appears in \(|A| \), \( |B| \) and subtracted in the \(|A \cap B|\) term (i.e. 1+1-1) times.
A similar result applies to probability and follows from the fundamental properties of probability measure which we look at in more detail in the Stochastic Calculus course
Show that $$P(A \cup B) = P(A)+P(B)-P(A \cap B)$$
Proof.
Firstly we split \( A \) and \( B \) into disjoint sets
\begin{align}
A &= A\backslash B + A \cap B \\
\implies P(A) &= P(A\backslash B) + P(A \cap B) \\
\end{align}
\begin{align}
B &= B\backslash A + A \cap B \\
\implies P(B) &= P(B\backslash A) + P(A \cap B) \\
\end{align}
Also we can split \( A \cup B \) into 3 disjoint sets,
\begin{align}
A \cup B &= A\backslash B + A \cap B + B\backslash A \\
\implies P(A \cup B) &= P(A\backslash B) + P(A \cap B) + P(B\backslash A) \\
\end{align}
From this follows the result.
Now consider adding one more set so we have \( A, B, C \). \begin{align} &|A \cup B \cup C| =\\ &|A| + |B| + |C| – \\ &|A \cap B| – |A \cap C| – |B \cap C| +\\ &|A \cap B \cap C| \end{align} This works as follows. If an item is only in one set, A say, and no other then it is counted exactly once. If an item is in exactly two sets and no other e.g. A and B, then it is counted once in the \( |A| \) term, once in the \( |B| \) and subtracted in the \( |A \cap B |\) term i.e. it is also counted once. Finally if a term is in all three sets then it is counted once in \( |A| \), once in \( |B| \) and once in \( |C| \) ( three times) and then it is subtracted in each of the intersection terms \(|A \cap B|\), \(|A \cap C|\) and \(|B \cap C|\) (three times), so these cancel out, and it is present once in the triple intersection \( |A \cap B \cap C| \)
In general
\begin{align*}
&P(\cup_{i=1}^{i=n} A_i)= \\
&\sum_{i=1}^{i=n} P(A_i) – \sum_{i_1 < i_2} P(A_{i_1} \cap A_{i_2})\\
&+…+ (-1)^{r+1} \sum_{i_1 <…< i_r} P( A_{i_1} \cap … \cap A_{i_r})\\
&+… + (-1)^{n+1} P( A_{1} \cap … \cap A_{n})
\end{align*}
Proof.
with proceed by using proof by induction.
We know the result holds for n = 2 which we showed above. Lets assume that the result holds for all \( n \leq N \)
and we will deduce it is true for \( N+1 \).
\begin{align}
P(\cup_{i=1}^{i=N+1} A_i)&= P(A_{N+1}\backslash \cup_{i=1}^{i=N} A_i) + P(\cup_{i=1}^{i=N} A_i) \text{(disjoint sets)}\\\\
P(A_{N+1}\backslash \cup_{i=1}^{i=N} A_i) &= P(A_{N+1}\backslash \cup_{i=1}^{i=N} A_i \cap A_{N+1}) \\
& = P(A_{N+1}) – P(\cup_{i=1}^{i=N} A_i \cap A_{N+1}) \\\\
\end{align}
so that
\( P(\cup_{i=1}^{i=N+1} A_i)= P(A_{N+1}) – P(\cup_{i=1}^{i=N} A_i \cap A_{N+1}) + P(\cup_{i=1}^{i=N} A_i) \)
Expanding the RHS using the expansion (which we assumed true for \( n \leq N \) although a bit tedious the result follows.
Example 1.
This is a classic hat problem which is solved using the inclusion exclusion principle.
n people toss their hats into a bin. You randomly return one hat to each person. Find the probability that nobody gets their own hat back.
Let \( A_i \) be the event that ith person gets his own hat back so we are trying to calculate \( 1 – P(\cup A_i) \)
\begin{align}
P(\cup A_i) &= \sum P(A_i) – \sum_{i < j} P(A_i \cup A_j)+…+P(A_1 \cup …\cup A_n) \\
& = n.\frac{1}{n} – \frac{1}{n}\frac{1}{n-1}\binom{n}{2}+\frac{1}{n}\frac{1}{n-1}\frac{1}{n-3}\binom{n}{3}\\
&+…-(-1)^{n}\frac{1}{n!}\\
&=1-\frac{1}{2!}+\frac{1}{3!}-…-(-1)^{n}\frac{1}{n!} \\
& \approx \exp(-1) \text{(taylor expansion of } e^x \text{ about } x=0)
\end{align}
so \( 1 – P(\cup A_i) \approx 1 – \exp(-1) \)