Inclusion-Exclusion Principle
For any events in the same probability space, the inclusion-exclusion principle states that the probability of their union can be calculated by alternately adding and subtracting the probabilities of their intersections. Formally,
Intuition
Consider 3 events, , , and . You would be quick to say that , just like I have, dozens of times. However, keep in mind that this only holds for mutually exclusive/disjoint events (with no overlaps). For any general events , , and , we can visualize the sample space as
\usepackage{tikz}
\begin{document}
\begin{tikzpicture}[scale = 0.75]
% Draw the box (sample space)
\draw[thick] (0, 0) rectangle (10, 8) node[below left] {$\Omega$};
% Draw the circles (different sizes)
\draw[thick] (3, 5) circle (2.5cm); % Circle A (smaller)
\node at (3, 5) {$A$};
\draw[thick] (7, 5) circle (3cm); % Circle B (medium)
\node at (7, 5) {$B$};
\draw[thick] (5, 2) circle (2cm); % Circle C (smallest)
\node at (5, 2) {$C$};
% Fill the pairwise intersections
% Intersection of A and B
\begin{scope}
\clip (3, 5) circle (2.5cm);
\clip (7, 5) circle (3cm);
\fill[gray, opacity=0.25] (0, 0) rectangle (10, 8);
\end{scope}
\node at (4.75, 5) {$A \cap B$};
% Intersection of A and C
\begin{scope}
\clip (3, 5) circle (2.5cm);
\clip (5, 2) circle (2cm);
\fill[gray, opacity=0.25] (0, 0) rectangle (10, 8);
\end{scope}
\node at (4, 3.2) {$A \cap C$};
% Intersection of B and C
\begin{scope}
\clip (7, 5) circle (3cm);
\clip (5, 2) circle (2cm);
\fill[gray, opacity=0.25] (0, 0) rectangle (10, 8);
\end{scope}
\node at (5.75, 3) {$B \cap C$};
% Fill the three-way intersection
\end{tikzpicture}
\end{document}Let’s consider and only. The two events yield the sample space
\usepackage{tikz}
\begin{document}
\begin{tikzpicture}[scale = 0.75]
% Draw the box (sample space)
\draw[thick] (0, 0) rectangle (10, 8) node[below left] {$\Omega$};
% Draw the circles (different sizes)
\draw[thick] (3, 5) circle (2.5cm); % Circle A (smaller)
\node at (3, 5) {$A$};
\draw[thick] (7, 5) circle (3cm); % Circle B (medium)
\node at (7, 5) {$B$};
% Fill the pairwise intersections
% Intersection of A and B
\begin{scope}
\clip (3, 5) circle (2.5cm);
\clip (7, 5) circle (3cm);
\fill[gray, opacity=0.25] (0, 0) rectangle (10, 8);
\end{scope}
\node at (4.75, 5) {$A \cap B$};
\end{tikzpicture}
\end{document}We can quickly infer that
\mathbb{P}[A] + \mathbb{P}[B]&=\Big(\mathbb{P}[A \cap \bar{B}]+\mathbb{P}[A \cap B]\Big) +\Big(\mathbb{P}[\bar{A} \cap B]+\mathbb{P}[A \cap B]\Big) \\ &= \mathbb{P}[A \cap \bar{B}]+\mathbb{P}[A \cap \bar{B}]+2\mathbb{P}[A \cap B]. \end{align}$$ where the joint probability $\mathbb{P}[A \cap B]$ is counted twice since it is a partition of both $A$ and $B$. This yields an overestimation. As such, we must subtract it, giving rise to the inclusion-exclusion principle. In the case of 3 events, things become a little complicated, but still understandable. While actual mathematical calculations can be done, they are complicated and I would rather make a sequential list of what's happening. In essence, I partition each event into 3 regions. Then: 1. I add $\mathbb{P}[A]$, $\mathbb{P}[B]$, and $\mathbb{P}[C]$ together. The pairwise intersections $\mathbb{P}[A \cap B]$, $\mathbb{P}[A \cap C]$, and $\mathbb{P}[B \cap C]$ appear exactly once. This means that $\mathbb{P}[A \cap B \cap C]$ appears 3 times. Each event also consists of its own non-overlapping part, as well as an overlapping part that excludes $\mathbb{P}[A \cap B \cap C]$ in order to form a valid partition. 2. I subtract $\mathbb{P}[A \cap B]$, $\mathbb{P}[A \cap C]$, and $\mathbb{P}[B \cap C]$. This leaves us with a gap where $\mathbb{P}[A \cap B \cap C]$ must be. 3. I add $\mathbb{P}[A \cap B \cap C]$ in order to fill the gap and get $\mathbb{P}[A \cup B \cup C]$. # Examples >[!example] A Night in Las Vegas > >Casinos advertise the probability of rolling your number on a fair 6-sided die in 3 rolls as $\mathbb{P}[A \cup B \cup C]=3 \times \frac{1}{6}$. This is wrong, since dice rolls aren't mutually exclusive, and therefore the probability of rolling your number on multiple rolls is counted more than once. Therefore, the actual probability is: >$$ >\begin{equation} >\begin{aligned} >\mathbb{P}[A \cup B \cup C] =& \space \mathbb{P}[A]+\mathbb{P}[B]+\mathbb{P}[C] - \\ & - \mathbb{P}[A \cap B]-\mathbb{P}[A \cap C]-\mathbb{P}[B \cap C] + \\ & + \mathbb{P}[A \cap B \cap C] \approx 0.42 >\end{aligned} \end{equation} >$$ >This can also be represented using the following diagram of a probability space: >```tikz >\begin{document} >\begin{tikzpicture}[domain=0:4] >\draw[] (0, 0) ellipse (4.25 and 2.25) node[left]{}; >\draw[] (0, 0.5) circle (1) node[above]{$A$}; >\draw[] (-0.6, -0.5) circle (1) node[below]{$B$}; >\draw[] (0.4, -0.5) circle (1) node[below]{$C$}; >\draw[->] (0,0) -- (0,-1.6) node[below]{$A \cap B \cap C$}; >\end{tikzpicture} >\end{document} >``` >The 3 events overlap 3 times ($A \cap B$, $B \cap C$, $C \cap A$). Therefore, the pairwise intersections of all events have to be removed. After this, a hole is left in the middle, which is filled by the intersection of all 3 events ($A \cap B \cap C$). >[!example] Joint Occurrence > >You know that at least one of the events $A_{i}, \space i = 1,\ldots,N$, is certain to occur, but certainly no more than two occur. $N$ is an integer $\geq 2$. Show that if the probability of occurrence of any single event is $p$, and the probability of joint occurrence of any two distinct events is $q$, we have $p \geq \frac{1}{N}$, and $q \leq \frac{2}{N(N-1)}$. > >>[!example] Solution >>We know that: >>1. One of the events $A_{i}$ is certain to occur with $\mathbb{P}(A_{i})=p$. >>2. No more than two events $A_{i} \cap A_{j}$ can occur, and $\mathbb{P}(A_{i} \cap A_{j})=q$. >>3. Since at least one event is certain to occur, $\mathbb{P}\Big[\bigcup^{N}_{i=1} A_i\Big]=1$ >> >>We proceed using the inclusion-exclusion principle. We know that: >>$$1=\sum^{N}_{i=1}\mathbb{P}(A_{i})-\sum^{}_{i < j}\mathbb{P}(A_{i} \cup A_{j}).$$ >>There are exactly $\binom{N}{2}$ ($N$ choose two) pairs of distinct events $A_{i} \cap A_{j}$. Therefore, >>$$Np - \frac{N!}{2(N-2)!}=Np - \frac{N(N-1)}{2}q=1.$$ >>Since the difference equation results in a positive sum, $Np \geq 1 \iff p \geq \frac{1}{N}$. Additionally, $q=\frac{2(Np-1)}{N(N-1)}$. For the minimum value of $p \geq \frac{1}{N}$, this equates to $q=\frac{2(0)}{N(N-1)}$