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

Abstract

The probability of union events is always important in management science. Many real life applications use such probability in their core implementations. The most popular method to calculate the probability of union events is the Inclusion-Exclusion Principle (IEP), which originates from the idea of Abraham de Moivre (1718). However, the computation complexity is exact O(2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> ), and no matter what the events are, the complexity order can not be decreased. A much efficient method namely Recursive Inclusion-Exclusion Principle (RIEP) was constructed by rearranging its equation to its recursive form. The computation complexity is also O(2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> ) in the worse cases, but it usually has 10 times efficiency than IEP in the normal cases. This paper proposed a novel reduction method for the RIEP to calculate the probability of union events, which can obtain over 100 times efficiency than RIEP in normal cases, and in the worse cases, it has at least the same complexity as that of RIEP. Some benchmarks on network reliability applications show that the proposed approach is very efficient.