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(i=1kAi)=i=1kP(Ai)1i<jkP(AiAj)++(1)k+1P(A1A2Ak). 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 A be the event that the card is a queen, and let B B be the event that the card is a heart. Then P(AB)=P(A)+P(B)P(AB) 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)=113 P(A) = \frac{1}{13} , and since there are 4 suits in the deck, P(B)=14 P(B) = \frac{1}{4} . There is only one card that is both a queen and a heart, so P(AB)=152 P(A \cap B) = \frac{1}{52} . Therefore,

P(AB)=14+113152=1652=413. 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

(110)+(112)++(1110). \binom{11}{0} + \binom{11}{2} + \cdots + \binom{11}{10}.

We can use the identity i=0n2(n2i)=2n1 \sum\limits_{i=0}^{\frac{n}{2}} \binom{n}{2i} = 2^{n-1} to see this sum is 210. 2^{10}. There are 211 2^{11} different possible results for all coin flips, so the probability is 210211=12 \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 (56)3 \left(\frac{5}{6}\right)^3 , since each roll is independent and there is a 56 \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(56)3 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.

Note by Calvin Lin
5 years, 7 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

For the second problem, I had a different approach. Say the fair coin is flipped 1010 times. Now the number of heads is either even or odd. In each case, to maintain the number of heads, there must be only one outcome from the 11th11^{th} flip. Thus, the first 1010 flips yield 2102^{10} outcomes, with the 11th11^{th} yielding 11 outcome. Total number of outcomes =211=2^{11}. Thus, the probability of an even number of heads is 210211=12\frac{2^{10}}{2^{11}}=\frac{1}{2}.

Nanayaranaraknas Vahdam - 5 years, 6 months ago

Log in to reply

Also, I have another query. Is my logic correct in the following solution.

The probability of a head is 12\frac12. Now, in 1111 tosses, there are two mutually exclusive outcomes. Either the number of heads is even or odd. Since the probability of both is equal. Thus, the probability of the number of heads is even is 12\frac12.

Nanayaranaraknas Vahdam - 5 years, 6 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...