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
    $\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
4
$\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$
  • $\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$ – Exc 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

Not the answer you're looking for? Browse other questions tagged or ask your own question.