a repository of mathematical know-how

To compute the probability that exactly k of n events occur, use generalized inclusion-exclusion

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 exactly k of these events occur. That is, you would like to compute the probability p_{[m]} of the set of samples that belong to exactly k of these sets. One can use the following generalized inclusion-exclusion formula to accomplish this:

 p_{[m]}= \sum_{k=0}^{N-m} (-1)^{k} \binom{ m+ k}{m} \sum_{1\le i_1 < i_2 < \cdots < i_{m+k} \le n } P\left( \cap_{j=1}^{m+k} A_{i_j}\right)

The formula looks complicated, but if the intersection probabilities P\left( \cap_{j=1}^k A_{i_j}\right) are simple to compute it gives a simple method to compute the desired probability. It can be useful in problems where it is not easy to use recursion or other techniques and when P has a complex dependence structure. In its limitations and usefulness it is similar to the ordinary inclusion exclusion principle.


Elementary probability.

Example 1

General discussion


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