a repository of mathematical know-how

To compute probabilities of unions and intersections, use the inclusion-exclusion formula

Stub iconThis article is a stub.This means that it cannot be considered to contain or lead to any mathematically interesting information.

Quick description

Suppose that A_1, A_2,..., A_n are events and you want to calculate the probability that at least one A_i holds. In set-theoretic terms, we are trying to calculate \mathbb{P}(A), where A is the union A_1\cup\dots\cup A_n of these events. If the events A_i overlap, this may look difficult, but often it can be computed using the inclusion-exclusion principle, which states that

 P(A) = \sum_{k=1}^n (-1)^{k+1} \sum_{1\le i_1 < i_2 <\cdots<i_k\le n} P\left( \cap_{j=1}^k A_{i_j} \right).

Although this formula appears complicated, what it gives is a way of calculating the probability of a union if you know the probabilities of intersections. Thus, for the method to be useful, it must be simple to compute the probabilities of the intersections \cap_{j=1}^k A_{i_j}.


Elementary probability theory.

Example 1

General discussion

Almost all expectation/probability computations can be embedded into a larger problem of a family of problems of the same kind and the larger problem will give a recursion [a reference to an article on this principle]. Sometimes, this recursion is not particularly simple to study. This will happen if the event A has no simple sequential description, i.e., an algorithm that generates its elements. What we mean by `not simple' in the preceding sentence is this: the probability of the set of all possible ways to execute the i^{th} step of this description/algorithm depends in a complicated way on the previous steps [ reference to the examples]. The inclusion/exclusion principle can be especially useful in such situations.

We also note that inclusion/exclusion is a representation result: it gives the probability of A exactly in terms of the probability of intersections of the sets whose union is A. This is interesting for several reasons. First, there aren't many results that allow one to compute a probability exactly. Second, using the inclusion exclusion principle in a theoretical or computational argument causes no loss of information.


Post new comment

(Note: commenting is not possible on this snapshot.)

Before posting from this form, please consider whether it would be more appropriate to make an inline comment using the Turn commenting on link near the bottom of the window. (Simply click the link, move the cursor over the article, and click on the piece of text on which you want to comment.)