Let $A_1, A_2, \dots, A_n \subset \Omega$ be arbitrary subsets of a probability space. Let $P$ be a probability measure on $(\Omega, \mathscr{P}(\Omega))$Denote: $$ s_1=\sum\limits_{i=1}^{\infty} P(A_i), \ s_2=\sum\limits_{1\leq i<j }^{\infty} P(A_i \cap A_j), \ s_3=\sum\limits_{1\leq i < j< k }^{\infty} P(A_i \cap A_j \cap A_k), \dots $$

Prove the inclusion-exclusion formula: $$ P(A_1 \cup A_2 \cup \dots \cup A_n)=s_1 - s_2 + s_3 - \dots + (-1)^{n+1} s_n, $$ using the following.

Partition $\Omega$ into sets $A_1'\cap A_2' \cap \dots \cap A_n'$ where each $A_i'$ is either $A_i$ or $A_i^c$. Then count the number of times a set in the partition occurs in an $s_i$. For example, if $n=2$ the set $A_1\cap A_2$ occurs twice in $s_1$ and once in $s_2$. The following identity will be useful in the proof: $$ \sum\limits_{i=0}^{k} (-1)^i {{n}\choose i} = (-1)^k {{n-1}\choose k}, 1\leq k \leq n. $$

I've looked at a couple of proofs for inclusion-exclusion, but none of the ones that I have found seem to be similar to this approach. I am not sure how this partition could be helpful in calculating $P(A_1\cup A_2 \cup \dots \cup A_n).$

The idea I have so far is the following.

$P(A_1 \cup A_2 \cup \dots \cup A_n)=\sum\limits_j P(A_j^*)$ where $A_j^*$ denotes a set in the collection of the partition that includes all the partition sets, but $A_1^c \cap A_2^c \cap \dots \cap A_n^c$.

Now I believe I somehow want to count the number of times each of the partition sets appears in each $s_i$. I am not sure how to go about this for general $n$.

Any help would be much appreciated.


Claim: $\qquad P(A_1 \cup A_2 \cup \dots \cup A_n)=s_1 - s_2 + s_3 - \dots + (-1)^{n+1} s_n \qquad\qquad\qquad\qquad(1)$

Take any set $B$ in the partition composed of the intersection of $k$ of the $A_i$ sets and $n-k$ of the $A_i^c$ sets, for some $0\leq k\leq n$. It's easy to see that the set $B$ will occur in $s_1\; \binom{k}{1}$ times, in $s_2\; \binom{k}{2}$ times, $\ldots$, and in $s_k\; \binom{k}{k}$ times, and $0$ times in the other values: $s_{k+1},\ldots,s_n$.

Thus, for $k=0$ (which means $B=A_1^c\cap\cdots\cap A_n^c$) set $B$ is counted in the RHS of $(1)\; 0 $ times, and for $1\leq k\leq n,$ the count is:

$$\binom{k}{1} - \binom{k}{2} + \binom{k}{3} - \cdots +(-1)^{k+1}\binom{k}{k} = \binom{k}{0} - (1-1)^k = 1.$$

On the LHS of $(1)$ we have same count: $B$ is counted exactly once if it has at least one of the $A_i$ sets in it, and is counted zero times if it has none of the $A_i$ sets. This proves the result.


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.