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

See the article on inclusion-exclusion principle.

Login or register to post comments
3452 reads