9813

Probability of a Union by the Principle of Inclusion-Exclusion

This Demonstration calculates the probability that there is at least one element from each of at most six classes when a given number of elements is sampled without replacement from among all the elements. This probability can be expressed in terms of the probability of a union of events and is calculated using the principle of inclusion-exclusion.

SNAPSHOTS

  • [Snapshot]
  • [Snapshot]
  • [Snapshot]
  • [Snapshot]
  • [Snapshot]

DETAILS

Snapshot 1: This is an example from [1, p. 73]; the same example is also considered in [2, p. 237]. We have six professors, six associate professors, 10 assistant professors, and 12 instructors; the total number of people is 34. A committee of size six is formed randomly. What is the probability that there is at least one person from each rank on the committee? Snapshot 1 shows that the probability is 0.379031 or, as an exact number, .
Snapshot 2: In a lottery in the USA, five numbers are drawn from the numbers 1 to 59. What is the probability that one number is drawn from each of the five sets , , , , and ? (Each of these sets contains 12 numbers, except the last one that contains 11 numbers.) The probability is only 0.04556. If we choose only 1, 2, 3, or 4 random numbers, the probability that one number is drawn from each of the five sets is, naturally, zero. If we choose 40 random numbers, the probability that one number is drawn from each of the five sets is, to six decimal places, 1.0, but the exact probability shows that the probability becomes exactly 1 only if we choose 49 or more numbers. Indeed, the 48 numbers 1 to 48 can be drawn from the first four sets, but among 49 numbers, there must be some in each of the five sets.
Snapshot 3: In the lottery of Snapshot 2, what is the probability that at least one number is drawn from each of the four sets , , , and ? (These sets contain 15, 15, 15, and 14 numbers, respectively.) The probability is 0.2595.
Snapshot 4: In the same lottery, what is the probability that at least one number is drawn from each of the three sets , , and ? (These sets contain 20, 20, and 19 numbers, respectively.) The probability is 0.6471.
Snapshot 5: Again in the same lottery, what is the probability that at least one number is drawn from each of the two sets and ? (These sets contain 30 and 29 numbers, respectively.) The probability is 0.9478. The probability is the same if the two sets are, say, and . (These sets also contain 30 and 29 numbers, respectively).
In this Demonstration, we have elements in at most six classes. We take a given number of elements at random without replacement from among all of the elements. What is the probability that we get at least one element from each class? Let be the event that we get at least one element from class . We want to calculate . By de Morgan's law, this probability can also be written as . Thus, we arrive at the probability of a union, where is the complement of , that is, is the event that we get no elements from class .
The probability of a union can be calculated by using the principle of inclusion-exclusion. For example,
,
,
In sampling without replacement, the probabilities in these formulas can easily be calculated by binomial coefficients. In the example of Snapshot 1, we have to use the third formula above. The probability that we get no professors is , the probability that we get no professors and no associate professors is , the probability that we get no professors, no associate professors, and no assistant professors is , and so on.
References
[1] S. Ghahramani, Fundamentals of Probability with Stochastic Processes, 3rd ed., Upper Saddle River, NJ: Pearson, 2005.
[2] P. J. Nahin, Digital Dice: Computational Solutions to Practical Probability Problems, Princeton, NJ: Princeton University Press, 2008.
    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.









 
RELATED RESOURCES
Mathematica »
The #1 tool for creating Demonstrations
and anything technical.
Wolfram|Alpha »
Explore anything with the first
computational knowledge engine.
MathWorld »
The web's most extensive
mathematics resource.
Course Assistant Apps »
An app for every course—
right in the palm of your hand.
Wolfram Blog »
Read our views on math,
science, and technology.
Computable Document Format »
The format that makes Demonstrations
(and any information) easy to share and
interact with.
STEM Initiative »
Programs & resources for
educators, schools & students.
Computerbasedmath.org »
Join the initiative for modernizing
math education.
Step-by-step Solutions »
Walk through homework problems one step at a time, with hints to help along the way.
Wolfram Problem Generator »
Unlimited random practice problems and answers with built-in Step-by-step solutions. Practice online or make a printable study sheet.
Wolfram Language »
Knowledge-based programming for everyone.
Powered by Wolfram Mathematica © 2014 Wolfram Demonstrations Project & Contributors  |  Terms of Use  |  Privacy Policy  |  RSS Give us your feedback
Note: To run this Demonstration you need Mathematica 7+ or the free Mathematica Player 7EX
Download or upgrade to Mathematica Player 7EX
I already have Mathematica Player or Mathematica 7+