Tricki
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}.

Prerequisites

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.