How to extend the Inclusion Exclusion Principle to an XOR situation

Question

For calculating the probability of the union of independent events, $P(A_1\cup A_2\cup A_3\cup A_4)$ one can use the Inclusion Exclusion principle:

$$ \eqalign{ P\Bigl(\bigcup_{i=1}^n A_i\Bigr) = \sum_{i\le n} P(A_i) - &\sum_{i_1<i_2} P(A_{i_1}\cap A_{i_2}) +\sum_{i_1<i_2<i_3} P(A_{i_1}\cap A_{i_2}\cap A_{i_3}) - \cr &\cdots+ (-1)^{n}\sum_{i_1<i_2<\cdots<i_{n-1} } P(A_{i_1}\cap\cdots\cap A_{i_{n-1}} )\cr&\qquad\qquad + (-1)^{n+1}P(A_1\cap A_2\cap\cdots\cap A_n)}. $$

How do we extend this to the case where we want the probability of one and only one of the events occurring (an XOR scenario)?

For a little clarification on my specific application, I am trying to use a recursive formula in Python to calculate P( A XOR B XOR C XOR ...):

def inclusionExclusion(P,n):
    if n < 1:
        return 0 #error state
    elif n == 1:
        return P
    else:
        temp = inclusionExclusion(P,n-1)
    return temp + P - temp*P   

This works (caveat: this is for when all events have the same probability, P, of occuring) for the inclusive or case, but not for the exclusive or case.

Further, if I want the Probability of $(A_1 \& A_2)\ OR\ (A_1 \& A_3)\ OR\ (A_1\&A_4) $, i.e. two and only two at a time, or three and only three at a time, how would I go about it?

Answer 1

Firstly, $XOR$ for $2$ or more operands is defined as (Source: Wikipedia)

XOR is true whenever an odd number of inputs is true. A chain of XORs—a XOR b XOR c XOR d (and so on)—is true whenever an odd number of the inputs are true and is false whenever an even number of inputs are true.

This differs to your use if it. I'll assume you mean "exactly one of a set of events". Then,

\begin{eqnarray*} P(\text{Exactly one of $\{A_1,\ldots,A_n\}$}) &=& P\left(\bigcup_{i=1}^{n}{\left(A_i \bigcap_{j=1,j\neq i}^{n}{A_j^c} \right)} \right) \\ && \\ &=& \sum_{i=1}^{n}{P\left(A_i \bigcap_{j=1,j\neq i}^{n}{A_j^c} \right)} - \sum_{i\lt k}{P\left(\left(A_i \bigcap_{j=1,j\neq i}^{n}{A_j^c} \right) \bigcap \left(A_k \bigcap_{l=1,l\neq k}^{n}{A_l^c} \right)\right)} \\ && + \cdots \qquad\qquad\qquad\qquad\qquad\text{by Inclusion-Exclusion} \\ && \\ &=& \sum_{i=1}^{n}{P\left(A_i \bigcap_{j=1,j\neq i}^{n}{A_j^c} \right)} \\ && \qquad\text{since in all but the first term there is some $m$} \\ && \qquad\text{for which $A_m \cap A_m^c$ appears.} \\ \end{eqnarray*}

This result is fairly obvious from the event definition without this Inclusion-Exclusion derivation.

The corresponding result for "Exactly $2/3/\cdots\; $ of $ \{A_1,\ldots,A_n\}$" is similar. E.g.

$$P(\text{Exactly two of $\{A_1,\ldots,A_n\}$}) = \sum_{i\lt j}^{n}{P\left(A_i \bigcap A_j \bigcap_{k=1,k\neq i,j}^{n}{A_k^c} \right)}.$$

Note that these results simplify in certain cases: (a) if the events $A_i$ are independent, (b) the events $A_i$ have the same probability $p$. E.g. if both (a) and (b) are true then

$$P(\text{Exactly two of $\{A_1,\ldots,A_n\}$}) = \binom{n}{2}p^2(1-p)^{n-2}.$$