Recursive inclusion exclusion principle

Question

The inclusion exclusion principle is as follows:

$P\Bigl(\bigcup_{i=1}^n E_i\Bigr) = \sum_{i\le n} P(E_i) - \sum_{i_1<i_2}P(E_{i_1}\cap E_{i_2})+\sum_{i_1<i_2<i_3}P(E_{i_1}\cap E_{i_2}\cap E_{i_3}) \dots$

is there any way to write this equation recursively?

Answer 1

Yes

based on Reduced Recursive Inclusion-exclusion Principle for the probability of union events

let

$π(Y_1, Y_2,...,Y_n) ≡ Pr(Y_1∪Y_2∪···∪ Y_n)$

be the function of probability of union events. According to the equivalent rearrangement, we have the following definition of recursive inclusion-exclusion principle:

$\pi(\emptyset) = 0$

$π(A_1) = Pr(A_1)$, for $n = 1$

$π(A_1, A_2,...,A_n) = \sum_{i=1}^n{Pr(A_i)−π(A_1 ∩ A_i, A_2 ∩ A_i,...,A_{i−1} ∩ A_i)}$, for $n > 1$

where $π(•)$ is a recursive function