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

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.

12087 reads
Subscribe

Comments

Post new comment

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