Probabilistic Inclusion-Exclusion

Definition

Probabilistic Principle of Inclusion and Exclusion

One of our best tools to approach problems involving events that are not mutually exclusive is the Principle of Inclusion and Exclusion. The probabilistic version of this principle is:

$P(\cup_{i=1}^{k} A_i)= \sum\limits_{i=1}^{k} P(A_i) - \sum\limits_{1 \leq i < j \leq k} P(A_i \cap A_j) + \cdots + (-1)^{k+1} P(A_1 \cap A_2 \cap \cdots \cap A_k).$

In general, techniques for solving counting problems are also useful for solving probability problems. We have seen examples of how the Rule of Sum and Rule of Product have been used to calculate probabilities. As for counting problems, it is sometimes easier to determine the probability of the complement of the set of interest.

Worked Examples

1. A card is drawn from a standard deck of cards. What is the probability that the card drawn is a queen or a heart?

Solution: Let $A$ be the event that the card is a queen, and let $B$ be the event that the card is a heart. Then $P(A \cup B) = P(A) + P(B) - P(A \cap B)$. Since there are 13 different ranks of cards in the deck, $P(A) = \frac{1}{13}$, and since there are 4 suits in the deck, $P(B) = \frac{1}{4}$. There is only one card that is both a queen and a heart, so $P(A \cap B) = \frac{1}{52}$. Therefore,

$P(A \cup B) = \frac{1}{4} + \frac{1}{13} - \frac{1}{52} = \frac{16}{52} = \frac{4}{13} .$

2. A fair coin is flipped 11 times. What is the probability that the number of heads is even?

Solution: The number of ways to get an even number of heads is

$\binom{11}{0} + \binom{11}{2} + \cdots + \binom{11}{10}.$

We can use the identity $\sum\limits_{i=0}^{\frac{n}{2}} \binom{n}{2i} = 2^{n-1}$ to see this sum is $2^{10}.$ There are $2^{11}$ different possible results for all coin flips, so the probability is $\frac{2^{10}}{2^{11}} = \frac{1}{2}$.

3. What is the probability that after rolling a die three times, at least one 6 is rolled?

Solution: We could do this calculation using the principle of inclusion and exclusion, but what happens if the die is rolled ten times rather than three times? The calculations would become very involved. Instead, we can efficiently calculate the complement probability. The probability that we do not see 6 after rolling three times is simply $\left(\frac{5}{6}\right)^3$, since each roll is independent and there is a $\frac{5}{6}$ chance that we don’t get a 6 on each roll. So the probability that we do see a 6 is $1 - \left(\frac{5}{6}\right)^3$. If we replaced three with any number in the question, we can easily see how our answer will change.