6
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ You do not say the source but this seems quite misleading (as noted by others, 2. and 3. are bogus). A direct approach is to consider $U=\bigcup\limits_{k=1}^nA_k$ and to note that $$1-\mathbf 1_U=\prod_{k=1}^n(1-\mathbf 1_{A_k}).$$ Expanding the RHS and noting that $P(A)=E(\mathbf 1_A)$ for every event $A$ and that $E(\ )$ is linear, one gets the result very soon. $\endgroup$ – Did Sep 20 '15 at 14:45
3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Nice answer. Just one doubt though, why is it WLOG D_{k,i} are contained in A_1 , ..., A_k for all i ? $\endgroup$ – user145003 Sep 20 '15 at 18:18
  • 1
    $\begingroup$ @Exc Not for all $i$. I mean for some particular $k$ and $i$. Sorry if that was confusing. I've updated that part to clarify. If you assume they're in $A_1,\ldots,A_k$, it just makes it easier, notation-wise, to prove (3). It's not necessary though. You can choose any general list of $k$ sets if you prefer, say, $A_{r_i},A_{r_2},\ldots,A_{r_k}$. $\endgroup$ – Mick A Sep 21 '15 at 1:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy