[Math] Inclusion Exclusion Principle ( Probability )

combinatoricsinclusion-exclusionprobability

I'm familiar with the Inclusion / Exclusion Principle for general counting but for the life me I'm not able to show the probability version in an exercise I'm trying from a book. I've included a picture below to show my problem.

$\mathbf{1.42}$ The inclusion-exclusion identity of Miscellanea $1.8.1$ gets its name from the fact that it is proved by the method of inclusion and exclusion (Feller $1968$, Section IV.$1$). Here we go into the details. The probability $P(\cup_{i=1}^nA_i)$ is the sum of the probabilities of all the sample points that are contained in at least one of the $A_i$s. The method of inclusion and exclusion is a recipe for counting these points.

  1. Let $E_k$ denote the set of all sample points that are contained in exactly $k$ of the events $A_1,A_2,\ldots,A_n$. Show that $P(\cup_{i=1}^nA_i)=\sum_{i=1}^nP(E_i)$.
  2. If $E_1$ is not empty, show that $P(E_1)=\sum_{i=1}^nP(A_i)$.
  3. Without loss of generality, assume that $E_k$ is contained in $A_1,A_2,\ldots,A_k$. Show that $P(E_k)$ appears $k$ times in the sum $P_1$, $\binom{k}2$ times in the sum $P_2$, $\binom{k}3$ times in the sum $P_3$, etc.
  4. Show that $$k-\binom{k}2+\binom{k}3-\cdots\pm\binom{k}k=1\;.$$ (See Exercise $1.27$.)
  5. Show that parts $(1)-(3)$ imply $\sum_{i=1}^nP(E_i)=P_1-P_2+\cdots\pm P_n$, establishing the inclusion-exclusion identity.

Here we define

$$\begin{align*}P_1&=\sum_{i=1}^nP(A_i)\\
P_2&=\sum_{1\le i<j\le n}P(A_i\cap A_j)\\
P_3&=\sum_{1\le i<j<k\le n}P(A_i\cap A_j\cap A_k)\\
&\vdots\\
P_n&=P(A_1\cap A_2\cap\cdots\cap A_n)\;.
\end{align*}$$

(Original images here and here.)

Nearly every proof I've seen of Inclusion / Exclusion has generally been with induction so I'm not entirely sure how to go about it from this direction.

To be specific, I'm only interested in part $(5)$ of this question. Could someone have a go at it using the way the book wants you to? Also, ignore part $(2)$, the question is a typo. Part $(5)$ should really be telling you to use $(1),(3)$, and $(4)$ to establish it.

Best Answer

I think $(3)$ is misleading. Since $E_k$ is the set of all sample points in exactly $k$ of the $A_i$ sets, $(3)$ makes no sense at all to me.

For $(3)$ I suggest we let each $E_k$ be a disjoint union:

$$E_k = \bigcup_{i=1}^{\binom{n}{k}} D_{k,i}$$

where each $D_{k,i}$ is the subset of $E_k$ where the $k$ $A_i$'s are a distinct $k$ of the sets $A_1,\ldots,A_n$.

Then, for $(3),\;$ we assume WLOG, for any given $k,i,\;$ that $D_{k,i}$ is contained in $A_1,\ldots,A_k$ (and in no others) and proceed as I think the author intends, with $D_{k,i}$ instead of $E_k$. Note that, by the additivity of probability:

$$P(E_k) = \sum_{i=1}^{\binom{n}{k}} P(D_{k,i}).$$

The idea of $(5)$ is that we have

\begin{eqnarray*} P\left(\bigcup_{i=1}^{n}A_i\right) &=& \sum_{k=1}^{n} P(E_k) \qquad\qquad\text{by $(1)$} \\ &=& \sum_{k=1}^{n} \sum_{i=1}^{\binom{n}{k}} P(D_{k,i}) \qquad\text{by $(3)$}\qquad\qquad\qquad\text{(*)} \\ \end{eqnarray*}

By $(3),\;$ any $P(D_{k,i})$ appears in the expression $P_1-P_2+P_3-\cdots\pm P_k,\;$ exactly $\left(k-\binom{k}{2}+\binom{k}{3}-\cdots\pm\binom{k}{k}\right)$ times, and this equals $1$ by $(4)$.

So, from $(*),\;$ we can conclude that $P(\cup_{i=1}^{n}A_i) = P_1-P_2+P_3-\cdots\pm P_n,\;$ as required.

Related Question