1.6.3 Inclusion-Exclusion Principle
The axiom of additivity allows us to find the probability of mutually exclusive events by simply adding their individual probabilities. However, when events are not mutually exclusive, we can not simply add the probabilities as doing so double counts the probability of any outcome which is in both events. For instance, if the probability of rain is 0.6 and the probability of wind is 0.8, the probability of rain or wind will be 1.4 which is incorrect as the probability can’t exceed 1. Since rain and wind can occur simultaneously, they are not mutually exclusive events, and therefore, their probabilities can’t be added directly.
This is where the inclusion-exclusion principle comes into play. This principle allows us to modify the additivity axiom by subtracting the probability of the intersection of the two events, ensuring an accurate calculation of the overall probability in such cases. The formula for the principle is:
Fig 1.15 depicts the union of two non-mutually exclusive events. The intersection area, , is included in both circles (highlighted by the brown region). To ensure accurate probability calculations, it is essential to subtract this overlapping area once, as it would otherwise be counted twice.
|
Inclusion-Exclusion Principle Proof
To prove the inclusion-exclusion principle, we will evaluate each side of its equation independently and establish their equality. The inclusion-exclusion equation is represented as follows:
(1.7)
Recall from section 1.3.7.1, The union of two sets and , denoted as , is a set that contains all the distinct elements that are either in , or in , or in both.
Using this definition, the union of two non-mutually exclusive events and , represented as , can be divided into three disjoint sets (Fig 1.16):
Together, the three sets contain every element of , thus:
(1.8)
The probability of the two sides of 1.8 can be expressed as:
(1.9)
By the axiom of additivity, we have:
(1.10)
Substituting 1.10 into 1.9 yields:
(1.11)
Now, let’s look at the events of the right-hand side of the inclusion-exclusion principle equation (1.7) and see if we get the same thing:
(1.12)
(1.13)
(1.14)
Substituting 1.12, 1.13 and 1.14 into the right-hand side of 1.7 yields
(1.15)
From 1.11 and 1.15, we prove the inclusion-exclusion principle:
If we do not subtract ( ), then we would be double counting the probability of set AandB, which would yield an incorrect probability of non-mutually exclusive events. |
Example 1.28. Let's revisit the school example that we previously employed in the discussion of the axiom of additivity (Example 1.26), where children were allowed to join only one club, but this time, we'll modify it: the children are now free to join both clubs if they wish. With this new arrangement, the children make the below enrollment choices:
- 5 children have joined the sports club.
- 4 children have joined the music club.
Our objective is to determine the probability that any given child from the class belongs to at least one of these clubs. To determine this probability, we would need to find the count of children who have either joined the sports club, the music club, or both.
Unlike Example 1.26, where memberships were mutually exclusive, children here may belong to both clubs. This can lead to an overlap. So, getting the overlap information is essential for accurate probability calculation, as without it, we don't know how many unique children have joined the clubs. For instance:
- If there is no overlap, the count of unique children who have joined the clubs is 9 (5 sports + 4 music).
- If all 4 music club members are also in the sports club, the count of unique children who have joined the clubs remains 5. (5 in sports, out of which 4 have also joined the music club).
Since we are discussing the inclusion-exclusion principle, let's exclude the case where there is no overlap i.e., none of the children joined both clubs. Let’s assume, that we get this additional information that 3 children have joined both clubs.
As children now have the option to join both clubs, Event , representing “a child joining the sports club” and Event , signifying “a child joining the music club”, are no longer mutually exclusive and we have a third event, , representing "a child joining both clubs", as represented by Fig 1.17.
With all the information we have, we can apply the Inclusion-Exclusion principle:
|
As illustrated in the pictorial representation of the inclusion-exclusion formula, the 3 children who are members of both clubs are represented in both Event S and Event M, depicted by the brown section in Fig 1.17. Therefore, to prevent double-counting these children, we must subtract this overlapping group once when calculating the union of Events S and M |
Thus, the probability can be calculated as:
Therefore, the probability that a randomly selected child is a member of either the sports or music club, or both, is 0.6 or 60%. In other words, 6 out of 10 children have joined at least one club, while 4 have not joined any club.
At the beginning of our problem, a simplistic approach might have led us to believe that 9 out of 10 children (5 in sports and 4 in music) were members of at least one club, leaving only 1 child not participating in any club. However, by applying the inclusion-exclusion principle, we accurately account for the children who are members of both clubs, thus avoiding any miscalculation.
The inclusion-exclusion principle can be expanded for more than two events, but it rather gets complex. For three non-mutually exclusive events , and the formula is:
|
The inclusion-exclusion principle also works for mutually exclusive events as the probability of mutually exclusive events is zero i.e., since the intersection of disjoint sets is an empty set (section 1.3.7.2). As such the formula () + () - ( ) reduces to () + (). |
As we can observe, calculating mutually exclusive events is less complex compared to non-mutually exclusive events, primarily because there is no overlap between the events. Another crucial property, which, if established, can significantly streamline probability calculations, is Independence. In the upcoming section, we will learn about this property and use it to calculate the probability of independent events.