11

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)$

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 got stuck at this point, maybe I could express $P(\cup_{i=1}^{n+1} A_i)=P((\cup_{i=1}^n A_i \setminus A_{n+1}) \cup A_{n+1})=P(\cup_{i=1}^n A_i \setminus A_{n+1})+P(A_{n+1})$ (1)

I can use the inductive hypothesis on the term $P(\cup_{i=1}^n A_i \setminus A_{n+1})$, so $P(\cup_{i=1}^n (A_i \setminus A_{n+1}))=\sum_{k=1}^n$ $\sum_{\mathcal J \subset \{1,...,n\}; |\mathcal J|=k} (-1)^{k+1}P(\bigcap_{i \in \mathcal J} (A_i\setminus A_{n+1}))$

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

I don't know to to take this expression to the one I want, which is

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

I would like to know how to continue this part of the exercise.

user100106
  • 3,493

2 Answers2

15

For an alternative to Hamou's approach—and one that's more similar to your initial idea—you can do the following: observe that $P(A\setminus B)=P(A)-P(A\cap B).$ So $$ \begin{aligned} P\left(\bigcup_{i=1}^{n+1}A_i\right)&=P\left(\bigcup_{i=1}^n A_i\right)+P\left(A_{n+1}\setminus\bigcup_{i=1}^n A_i\right)\\ &=P\left(\bigcup_{i=1}^n A_i\right)+P(A_{n+1})-P\left(\bigcup_{i=1}^n (A_i\cap A_{n+1})\right). \end{aligned} $$ Now apply the induction hypothesis to both unions in this last expression.

Will Orrick
  • 18,220
  • Thanks very much for your answer. I think I almost got it except from one minus sign. The last expression you wrote, using the IH, is equal to $\sum_{\mathcal J \subset {1,...,n}; |\mathcal J|=k} (-1)^{k+1}P(\bigcap_{i \in \mathcal J} A_i)+P(A_{n+1})-\sum_{\mathcal J \subset {1,...,n}; |\mathcal J|=k} (-1)^{k+1}P(\bigcap_{i \in \mathcal J} A_i \cap A_{n+1})$. – user100106 Aug 24 '14 at 18:53
  • On the other hand, the expression $\sum_{\mathcal J \subset {1,...,n+1}; |\mathcal J|=k} (-1)^{k+1}P(\bigcap_{i \in \mathcal J} A_i)$ can be separated in two (actually, three) terms: 1) all possible intersections between sets except $A_{n+1}$, and all combinations of intersections where $A_{n+1}$ is intersected. This is $\sum_{\mathcal J \subset {1,...,n}; |\mathcal J|=k} (-1)^{k+1}P(\bigcap_{i \in \mathcal J} A_i)+\sum_{\mathcal J \subset {1,...,n}; |\mathcal J|=k} (-1)^{k+1}P(\bigcap_{i \in \mathcal J} A_i \cap A_{n+1})+P(A_{n+1}).$ Why are they almost the same except for the minus? – user100106 Aug 24 '14 at 19:00
  • 2
    Those intersections that contain $A_{n+1}$ in your last expression are of size $k+1,$ not size $k.$ So instead of $(-1)^{k+1}$ you should have $(-1)^{k+2}.$ – Will Orrick Aug 24 '14 at 19:28
  • Can you tell me why doesn't $A_{n+1}$ stop us from applying the induction ? – domdrag Oct 14 '17 at 17:59
  • 2
    @JamesGroon the induction is on the number of terms in the union, which is $n$ for both unions. Under the induction hypothesis, the principle of inclusion-exclusion holds for unions of $n$ terms. By grouping terms, and simplifying some of them, the principle can be deduced for unions of $n+1$ terms. – Will Orrick Oct 14 '17 at 18:50
  • Aha so no matter which events we choose , the induction will hold as long as its $<=$ n. Thanks. – domdrag Oct 14 '17 at 19:37
3

Hint: For $n\Rightarrow n+1$: $A_1,\ldots,A_n,A_{n+1}$, take $B_1=A_1,\ldots,A_{n-1}=B_{n-1},B_n=A_n\cup A_{n+1}$ and apply the inductive hypothesis to $B_1,\ldots,B_n$.

Hamou
  • 6,745
  • I could arrive to $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 term equals to $\sum_{\mathcal J \subset {1,...,n-1}; |\mathcal J|=k} (-1)^{k+1}P(\bigcap_{i \in \mathcal J} B_i)+\sum_{\mathcal J \subset {1,...,n-1}; |\mathcal J|=k-1} (-1)^{k+1}P(\bigcap_{i \in \mathcal J} B_i \cap B_n)=\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+1}P(\bigcap_{i \in \mathcal J} A_i \cap (A_n \cup A_{n+1}))$ – user100106 Aug 23 '14 at 21:22
  • Could you help me to continue? Btw, thanks for the suggestion. – user100106 Aug 23 '14 at 21:22
  • 1
    For the second term $\cap_{i\in J}A_i\cap(A_n\cup A_{n+1})=\left(\cap_{j\in J}A_i\cap A_n\right)\cup \left(\cap_{j\in J}A_i\cap A_{n+1}\right)$ – Hamou Aug 23 '14 at 21:27
  • Sorry I keep asking, I am having problems reducing this expression to the one I want:$\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}))$ – user100106 Aug 23 '14 at 21:39
  • What is the number of part intersection here $\cap_{j\in J}A_i\cap A_n$ and here $\cap_{j\in J}A_i\cap A_{n+1}$ and here $\cap_{j\in J}A_i\cap A_n\cap A_{n+1}$? add its in the term corresponding with the cardinal. – Hamou Aug 23 '14 at 21:44
  • If I understood your question, the number of part intersection is $k$, but I am not so sure how to express these intersections, for example, I cannot say $\mathcal J \subset {1,...,n+1}$ for the expression $\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}))$ since I would be counting more probabilities. – user100106 Aug 23 '14 at 22:04
  • If $J\subset{1,\ldots,n-1}$ and $|J|=k$, then $J'=J\cup{n}\subset{1,\ldots,n}$ and $|J'|=k+1$... – Hamou Aug 23 '14 at 22:13