Tricki
a repository of mathematical know-how

Revision of To compute that exactly k of n events occur, use generalized inclusion-exclusion from Tue, 12/05/2009 - 22:55

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=1}^{N-m} (-1)^{k+1} \binom{ m+ k}{m} \sum_{1\le i_1 < i_2 < \cdots < i_k \le n } P\left( \cap_{j=1}^k A_{i_j}\right)

This formula is computationally useful if it is simple to compute the probabilities P\left( \cap_{j=1}^k A_{i_j}\right). For more information on this formula see the article on the simple inclusion-exclusion principle.

Prerequisites

Elementary probability.

Example 1

General discussion