Exclusion-inclusion formula in probability

[mahler1]

Homework Statement

Let $(\Omega,\mathcal F, P)$ be a probability space and let $A_1,A_2,...,A_n$ be events in $\mathcal F$.

Prove the following inclusion-exclusion formula

$P(\bigcup_{i=1}^nA_i)=\sum_{k=1}^n$ $\sum_{\mathcal J \subset \{1,...,n\}; |\mathcal J|=k} (-1)^{k+1}P(\bigcap_{i \in \mathcal J} A_i)$

The Attempt at a Solution

I am trying to prove this formula by induction; for $n=2$, let $A, B$ be two events in $\mathcal F$. We can write $A=(A \setminus B) \cup (A\cap B)$, $B=(B \setminus A) \cup (A\cap B)$, since these are disjoint unions, then

$P(A)=P(A \setminus B)+P(A\cap B)$ and $P(B)=P(B \setminus A)+P(A\cap B)$.

Now, $A \cup B$ can be expressed as $A \cup B= (A\setminus B) \cup (A \cap B) \cup (B \setminus A)$, which it's also union of disjoint sets, so

$P(A \cup B)=P(A \setminus B)+P(A\cap B)+P(B \setminus A)=P(A)+P(B)-P(A \cap B)$.

This proves that for $n=2$, the formula is correct.

Now, I want to show that the formula is true for $n \implies$ the formula is satisfied for $n+1$

I define $B_1=A_1,\ldots,B_{n-1}=A_{n-1},B_n=A_n\cup A_{n+1}$. We have

$P(\cup_{i=1}^n B_i)=\sum_{\mathcal J \subset \{1,...,n\}; |\mathcal J|=k} (-1)^{k+1}P(\bigcap_{i \in \mathcal J} B_i)$.

This equals to $\sum_{\mathcal J \subset \{1,...,n-1\}; |\mathcal J|=k} (-1)^{k+1}P(\bigcap_{i \in \mathcal J} A_i)+\sum_{\mathcal J \subset \{1,...,n-1\}; |\mathcal J|=k-1} (-1)^{k}P(\bigcap_{i \in \mathcal J} A_i \cap (A_n \cup A_{n+1}))$

$=\sum_{\mathcal J \subset \{1,...,n-1\}; |\mathcal J|=k} (-1)^{k+1}P(\bigcap_{i \in \mathcal J} A_i)+\sum_{\mathcal J \subset \{1,...,n-1\}; |\mathcal J|=k-1} (-1)^k(P(\bigcap_{i \in \mathcal J} A_i \cap A_n)+ P(\bigcap_{i \in \mathcal J} A_i \cap A_{n+1})-P(\bigcap_{i \in \mathcal J} A_i \cap A_n \cap A_{n+1}))$.

I don't know how to reduce this expression to the one I need to, which is:

$\sum_{\mathcal J \subset \{1,...,n+1\}; |\mathcal J|=k} (-1)^{k+1}P(\bigcap_{i \in \mathcal J} A_i)$


I would really appreciate some help to finish the problem.

 

[Ray Vickson]

Homework Statement

Let $(\Omega,\mathcal F, P)$ be a probability space and let $A_1,A_2,...,A_n$ be events in $\mathcal F$.

Prove the following inclusion-exclusion formula

$P(\bigcup_{i=1}^nA_i)=\sum_{k=1}^n$ $\sum_{\mathcal J \subset \{1,...,n\}; |\mathcal J|=k} (-1)^{k+1}P(\bigcap_{i \in \mathcal J} A_i)$

The Attempt at a Solution

I am trying to prove this formula by induction; for $n=2$, let $A, B$ be two events in $\mathcal F$. We can write $A=(A \setminus B) \cup (A\cap B)$, $B=(B \setminus A) \cup (A\cap B)$, since these are disjoint unions, then

$P(A)=P(A \setminus B)+P(A\cap B)$ and $P(B)=P(B \setminus A)+P(A\cap B)$.

Now, $A \cup B$ can be expressed as $A \cup B= (A\setminus B) \cup (A \cap B) \cup (B \setminus A)$, which it's also union of disjoint sets, so

$P(A \cup B)=P(A \setminus B)+P(A\cap B)+P(B \setminus A)=P(A)+P(B)-P(A \cap B)$.

This proves that for $n=2$, the formula is correct.

Now, I want to show that the formula is true for $n \implies$ the formula is satisfied for $n+1$

I define $B_1=A_1,\ldots,B_{n-1}=A_{n-1},B_n=A_n\cup A_{n+1}$. We have

$P(\cup_{i=1}^n B_i)=\sum_{\mathcal J \subset \{1,...,n\}; |\mathcal J|=k} (-1)^{k+1}P(\bigcap_{i \in \mathcal J} B_i)$.

This equals to $\sum_{\mathcal J \subset \{1,...,n-1\}; |\mathcal J|=k} (-1)^{k+1}P(\bigcap_{i \in \mathcal J} A_i)+\sum_{\mathcal J \subset \{1,...,n-1\}; |\mathcal J|=k-1} (-1)^{k}P(\bigcap_{i \in \mathcal J} A_i \cap (A_n \cup A_{n+1}))$

$=\sum_{\mathcal J \subset \{1,...,n-1\}; |\mathcal J|=k} (-1)^{k+1}P(\bigcap_{i \in \mathcal J} A_i)+\sum_{\mathcal J \subset \{1,...,n-1\}; |\mathcal J|=k-1} (-1)^k(P(\bigcap_{i \in \mathcal J} A_i \cap A_n)+ P(\bigcap_{i \in \mathcal J} A_i \cap A_{n+1})-P(\bigcap_{i \in \mathcal J} A_i \cap A_n \cap A_{n+1}))$.

I don't know how to reduce this expression to the one I need to, which is:

$\sum_{\mathcal J \subset \{1,...,n+1\}; |\mathcal J|=k} (-1)^{k+1}P(\bigcap_{i \in \mathcal J} A_i)$


I would really appreciate some help to finish the problem.

Instead of trying to jump immediately to the general case, first try the simple cases of going from n=2 to n=3 and from n=3 to n=4 (and no, I am not joking). That way, you will see what is happening, and be able to grasp how to go the the general case of n to (n+1).