Inclusion-exclusion formula

76 Views Asked by At

This is problem 1.8.13 in "One Thousand Exercises in Probability", I can't get this equal sign. $$\mathbb{P}(\bigcap_{i \in S}A_i\bigcap_{j \notin S} A_j^c) = \mathbb{P}(A_s) - \sum_{j \notin S} \mathbb{P}(A_{S \cup \{j\}})+\sum_{\substack{j<k \\j,k \notin S}}\mathbb{P}(A_{S \cup \{j,k\}})-\dotsb,$$where we write $A_S = \bigcap_{i \in S}A_i.$

If events $A_i$ are independent, then it is easy to show, but the events are not necessarily independent. Also by the inclusion-exclusion principle, isn't the first term the sum of $A_S$ and all $A_j^c$'s? I'm stuck step bros, help is much appreciated.

1

There are 1 best solutions below

0
On

If you look at the solution where they introduce inclusion-exclusion, you should notice that it doesn't actually look quite like the version of inclusion-exclusion proven in exercise 1.3.4 - instead of unions, we have intersections, and the events $A_j^c$ get swapped to $A_j$ across the equals sign. They have, in fact, relied on you to fill in some missing steps, possibly inspired by the solution to exercise 1.8.12 which takes complements to flip intersections and unions.

Notice that we can apply a simple decomposition and some de Morgan:

$$\begin{eqnarray} \mathbb{P}(A_S) & = & \mathbb{P}\left(A_S \cap \left(\bigcap_{j \notin S} A_j^c\right)\right) + \mathbb{P}\left(A_S \cap \left(\bigcap_{j \notin S} A_j^c\right)^c\right) \\ & = & \mathbb{P}\left(\bigcap_{i \in S} A_i \bigcap_{j \notin S} A_j^c\right) + \mathbb{P}\left(A_S \cap \left(\bigcup_{j \notin S} A_j\right)\right) \\ & = & \mathbb{P}\left(\bigcap_{i \in S} A_i \bigcap{j \notin S} A_j^c\right) + \mathbb{P}\left(\bigcup_{j \notin S} \left(A_S \cap A_j\right)\right)\end{eqnarray}$$

The first term is the thing on the left-hand side of the equation in the solution, and you can apply inclusion-exclusion from 1.3.4 to the second term, then rearrange everything to get the equation they state.

There's probably a neater way to get to the same point, but that's how I got to it.