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

Prerequisites

Elementary probability.

Example 1

General discussion