Sharad Dubey
Hi, I am a data scientist who believe that 'Torture the data and It'll confess everything'. I am working on image processing and Natural Language Processing.
1 min read 147 views

Inclusion-Exclusion Principle

Inclusion-Exclusion Principle_image

The Inclusion-Exclusion principle states that for two events A and B, \(P(AUB) = P(A) + P(B) - P(A\cap B)\)

This can easily be proven by considering two sets some parts of which is overlapping namely A and B. 

\(P(B - A) = P(B) - P(A \cap B)\)

This can be easily visualised using a venn diagram of two sets. Also, 

\(P(A U B) = P(A U (B-A))\)

              \(= P(A) + P(B-A)\)

               \(= P(A) + P(B) -P(A \cap B)\)

Morevoer, this can be generalised in the case of more than 2 sets. Which is stated as: 

\(|(A_1 U A_2 . . . . . . .A_n)| = \Sigma_{i = 1}^n(|A_i|) - \Sigma_{1<=i_1<i_2=<n}(|A_{i1} \cap A_{i2})|+. . . . . +(-1)^{n-1}(|A_1 \cap A_2 \cap. . . . . . . . \cap A_n|)\)

The Inclusion-Exclusion principle turns out to be of great use. It is used in finding probability of a null event, finding out the universal bounds for the probabilities and many other places.