1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Exclusion-inclusion formula in probability

  1. Aug 24, 2014 #1
    1. The problem statement, all variables and given/known data

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


    3. 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.
     
  2. jcsd
  3. Aug 24, 2014 #2

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    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).
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Exclusion-inclusion formula in probability
  1. Inclusion exclusion (Replies: 0)

Loading...