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

a repository of mathematical know-how

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

Title: *

Area of mathematics: *

A comma-separated list of areas of mathematics to which this article applies. Use ">" to tag in a subcategory. Example: Analysis > Harmonic analysis, Combinatorics

Keywords:

A comma-separated list of keywords associated with this article. Example: free group

Used in:

A comma-separated list of examples of where this technique is used. Example: Cauchy-Schwarz inequality

Parent articles:		Order

Body:

[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
[maths]
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).
[/maths]
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]

[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.

This is a stub

A stub is an article that is not sufficiently complete to be interesting.

Notifications

File attachments

Changes made to the attachments are not permanent until you save this post. The first "listed" file will be included in RSS feeds.

Attach new file:

Images are larger than 640x480 will be resized. The maximum upload size is 1 MB. Only files with the following extensions may be uploaded: jpg jpeg gif png svg.

Revision information

Log message:

An explanation of the additions or updates being made to help other authors understand your motivations.

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

Recent articles

Active forum topics

Recent comments