6
$\begingroup$

I need to use the principle of inclusion/exclusion to calculate the "OR" probability of a large number of events

$$ P( A_1 \cup A_2 \cup \dots \cup A_n ) $$

For two events the formula to use is (from Wikipedia http://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle#In_probability) :

$$P(A_1\cup A_2)=P(A_1)+P(A_2)-P(A_1\cap A_2) $$.

For three events :

$$ P(A_1\cup A_2\cup A_3)=P(A_1)+P(A_2)+P(A_3) -P(A_1\cap A_2)-P(A_1\cap A_3)-P(A_2\cap A_3)+P(A_1\cap A_2\cap A_3) $$

For n events :

$$ P\biggl(\bigcup_{i=1}^n A_i\biggr) {} =\sum_{i=1}^n P(A_i) -\sum_{i<j}P(A_i\cap A_j) \qquad+\sum_{i<j<k}P(A_i\cap A_j\cap A_k)- \cdots\ +(-1)^{n-1}\, P\biggl(\bigcap_{i=1}^n A_i\biggr) $$

The latter contains a very large number of terms, making it hard to compute. So I thought it might be possible to use a trick. If this works, I am surely not the first one to come up with this.

The idea, illustrated on 4-event example, is $$ P( A_1 \cup A_2 \cup A_3 \cup A_4 ) $$ is equivalent to $$ P( (A_1 \cup A_2) \cup (A_3 \cup A_4) )$$ is equivalent to $$ P( A_1 \cup A_2) + P( A_3 \cup A_4) - P( A_1 \cup A_2) * P( A_3 \cup A_4) $$ .

The 2-event unions can be computed by the formula above.

This can be applied to $n$ events also. The algorithm always unifies 2 events to a new event, which is then combined with another unified event. So each step reduces the number of events to $n/2$ or $n/2+1$ if $n$ is odd. The procedure is repeated until a single union probability remains.

This makes it possible to reduce the required computational steps to $ O(log n) $ (or something like that).

I have tested this by numerically comparing the results of the procedure for 3 events and 4 events. It seems to work.

So my questions are: Is this wrong? And is there any literature reference on this approach?

$\endgroup$
  • 1
    $\begingroup$ Shouldn't $P(A_1 \cup A_2) * P(A_3 \cup A_4)$ be $P((A_1 \cup A_2) \cap (A_3 \cup A_4))$, since your events are non-mutually exclusive? Then you have $P((A_1 \cap A_3) \cup (A_2 \cap A_3) \cup (A_1 \cap A_4) \cup (A_2 \cap A_4))$, so I don't think you can trivially extend the algorithm... $\endgroup$ – Hao Ye May 14 '14 at 23:58
  • $\begingroup$ The events are non-mutually exclusive, but independent. So $P(A_1\cap A_2) = P(A_1) P(A_2) $. $\endgroup$ – Hannes Planatscher May 15 '14 at 7:04
5
$\begingroup$

As @HaoYe's comment points out, your recursion via divide-and-conquer is not quite right: it is not the case that $$P(A_1\cup A_2\cup A_3\cup A_4) = P( A_1 \cup A_2) + P( A_3 \cup A_4) - P( A_1 \cup A_2) * P( A_3 \cup A_4)$$ but rather that $$P(A_1\cup A_2\cup A_3\cup A_4) = P( A_1 \cup A_2) + P( A_3 \cup A_4) - P\left(( A_1 \cup A_2) \cap ( A_3 \cup A_4)\right).$$ In any case, the principle of inclusion/exclusion gives a very pretty formula that rarely can be used in practice because the probabilities of all those various intersections are not easy to determine. One case where the probabilities can be calculated is when the $n$ events are mutually independent, but in this special case, the general formula should not be used at all!

For $n$ mutually independent events $A_1, A_2, \ldots, A_n$, use DeMorgan's theorem to write $$P\left(\bigcup_{i=1}^n A_i\right) = 1 - P\left(\bigcap_{i=1}^n A_i^c\right) = 1 - \prod_{i=1}^n P(A_i^c)= 1 - \prod_{i=1}^n \left[1 - P(A_i)\right] \tag{1}$$ and calculate $P(A_1\cup A_2\cup\cdots\cup A_n)$ using $n-1$ multiplications and $n+1$ subtractions. In other words, for Heaven's sake, resist the temptation to multiply out those terms in square brackets on the right because you will end up with the inclusion/exclusion formula which you should try to avoid at all costs.

$\endgroup$
  • 1
    $\begingroup$ You are right! I just compared the "DeMorgan formula" to the recursive approach and the results are exatly the same. So in summary recursion works, however only if the events are independent, BUT in this case there is the far simpler approach using DeMorgan. THANKS! $\endgroup$ – Hannes Planatscher May 15 '14 at 7:19
  • $\begingroup$ Hi - this was very helpful, but is there a way to do it with only 3 events? Ie, is it P(A1 or A2) + P(A3) - P((A1 or A2) AND A3)? That doesn't seem right... $\endgroup$ – keynesiancross Jul 28 '16 at 20:17
1
$\begingroup$

Nothing wrong with this approach. If you use floating point, you will want to or (add up) the two smallest remaining probabilities in each step in order to minimize the effect of rounding errors (floating point is most accurate when the values you add are of similar magnitude).

PS. Since (a or b or c or d) = ((a or b) or (c or d)), you don't need any literature reference. The correctness follows directly from associativity of OR.

$\endgroup$
  • $\begingroup$ I don't think the OP's formulas are correct. $\endgroup$ – Dilip Sarwate May 15 '14 at 2:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.