Editing Inclusion–exclusion principle (section)

==In probability==

In [[probability]], for events ''A''<sub>1</sub>, ..., ''A''<sub>''n''</sub> in a [[probability space]] <math>(\Omega,\mathcal{F},\mathbb{P})</math>, the inclusion–exclusion principle becomes for ''n''&nbsp;=&nbsp;2

:<math>\mathbb{P}(A_1\cup A_2)=\mathbb{P}(A_1)+\mathbb{P}(A_2)-\mathbb{P}(A_1\cap A_2),</math>

for ''n''&nbsp;=&nbsp;3

:<math>\mathbb{P}(A_1\cup A_2\cup A_3)=\mathbb{P}(A_1)+\mathbb{P}(A_2)+\mathbb{P}(A_3)-\mathbb{P}(A_1\cap A_2)-\mathbb{P}(A_1\cap A_3)-\mathbb{P}(A_2\cap A_3)+\mathbb{P}(A_1\cap A_2\cap A_3)</math>

and in general

:<math>\mathbb{P}\left(\bigcup_{i=1}^n A_i\right)=\sum_{i=1}^n \mathbb{P}(A_i) -\sum_{i<j}\mathbb{P}(A_i\cap A_j)+\sum_{i<j<k}\mathbb{P}(A_i\cap A_j\cap A_k) + \cdots +(-1)^{n-1} \mathbb{P}\left(\bigcap_{i=1}^n A_i\right),</math>

which can be written in closed form as

:<math>\mathbb{P}\left(\bigcup_{i=1}^n A_i\right)=\sum_{k=1}^n \left((-1)^{k-1}\sum_{I\subseteq\{1,\ldots,n\}\atop |I|=k} \mathbb{P}(A_I)\right),</math>

where the last sum runs over all subsets ''I'' of the indices 1, ..., ''n'' which contain exactly ''k'' elements, and

:<math>A_I:=\bigcap_{i\in I} A_i</math>

denotes the intersection of all those ''A<sub>i</sub>'' with index in ''I''.

According to the [[Boole's inequality#Bonferroni inequalities|Bonferroni inequalities]], the sum of the first terms in the formula is alternately an upper bound and a lower bound for the [[Sides of an equation|LHS]]. This can be used in cases where the full formula is too cumbersome.

For a general [[measure space]] (''S'',Σ,''μ'') and [[measurable]] subsets ''A''<sub>1</sub>, ..., ''A''<sub>''n''</sub> of [[finite measure]], the above identities also hold when the probability measure <math>\mathbb{P}</math> is replaced by the measure ''μ''.

===Special case===

If, in the probabilistic version of the inclusion–exclusion principle, the probability of the intersection ''A''<sub>''I''</sub> only depends on the cardinality of ''I'', meaning that for every ''k'' in {1,&nbsp;...,&nbsp;''n''} there is an ''a<sub>k</sub>'' such that

:<math>a_k=\mathbb{P}(A_I) \text{ for every } I\subset\{1,\ldots,n\} \text{ with } |I|=k,</math>

then the above formula simplifies to

:<math>\mathbb{P}\left(\bigcup_{i=1}^n A_i\right) =\sum_{k=1}^n (-1)^{k-1}\binom n k a_k </math>

due to the combinatorial interpretation of the [[binomial coefficient]] <math display="inline">\binom nk</math>. For example, if the events <math>A_i</math> are [[independent and identically distributed]], then <math>\mathbb{P}(A_i) = p</math> for all ''i'', and we have <math>a_k = p^k</math>, in which case the expression above simplifies to

:<math>\mathbb{P}\left(\bigcup_{i=1}^n A_i\right) = 1 - (1-p)^n. </math>

(This result can also be derived more simply by considering the intersection of the complements of the events <math>A_i</math>.)

An analogous simplification is possible in the case of a general measure space <math>(S, \Sigma, \mu)</math> and measurable subsets <math>A_1, \dots, A_n</math> of finite measure.

There is another formula used in [[Point process notation|point processes]]. Let <math>S</math> be a finite set and <math>P</math> be a random subset of <math>S</math>. Let <math>A</math> be any subset of <math>S</math>, then

<math display="block">\begin{aligned}
\mathbb{P}(P = A) &= \mathbb{P}(P \supset A) - \sum_{j_1 \in S \setminus A} \mathbb{P}(P \supset A \cup {j_1}) \\
&+ \sum_{j_1, j_2 \in S \setminus A \ j_1 \ne j_2} \mathbb{P}(P \supset A \cup {j_1, j_2}) + \dots \\
&+ (-1)^{|S|-|A|} \mathbb{P}(P \supset S) \\
&= \sum_{A \subset J \subset S} (-1)^{|J|-|A|} \mathbb{P}(P \supset J).
\end{aligned}
</math>