# Inclusion - exclusion-like inequality

Let $(\Omega,\mathcal{F},\mathbb{P})$ be some probabilistic space and $A_1,\ldots,A_n\in \mathcal{F}$. Is it true that:

$$\sum\limits_{i=1}^{n} \mathbb{P}(A_i)^2 - \sum\limits_{1\le i<j\le n}\mathbb{P}(A_i \cap A_j)^2+\ldots + (-1)^{n+1} \mathbb{P}(A_1 \cap A_2 \cap \ldots\cap A_n)^2\ge 0?$$

When $A_1,\ldots,A_n$ are independent, then we can write left side of this inequality as:

$$1-\prod\limits_{i=1}^{n} (1-\mathbb{P}(A_i)^2)\ge 0.$$

What happens in the general case?

Let $X_r$, for $r=1,2,\ldots,s$, be independent random elements of $\Omega$. We have $\text{Prob}\left(X_r\in E\right)=\mathbb{P}(E)$ for all $E\in\mathcal{F}$. Let $T$ be the event that there exists $i=1,2,\ldots,n$ such that $X_r\in A_i$ for every $r=1,2,\ldots,s$. Clearly, $0 \leq \text{Prob}(T) \leq 1$.
Now, by the Principle of Inclusion and Exclusion, $$\displaystyle\text{Prob}(T)=\sum_{k=1}^n\,(-1)^{k-1}\,\sum_{1\leq i_1<i_2<\ldots<i_k\leq n}\,\text{Prob}\left(X_r\in\textstyle\bigcap_{j=1}^k\,A_{i_j}\text{ for all }r=1,2,\ldots,s\right)\,.$$ Since $X$ and $Y$ are independent, $$\displaystyle\text{Prob}(T)=\sum_{k=1}^n\,(-1)^{k-1}\,\sum_{1\leq i_1<i_2<\ldots<i_k\leq n}\,\prod_{r=1}^s\,\text{Prob}\left(X_r\in\textstyle\bigcap_{j=1}^k\,A_{i_j}\right)\,.$$ Thus, $$\displaystyle\text{Prob}(T)=\sum_{k=1}^n\,(-1)^{k-1}\,\sum_{1\leq i_1<i_2<\ldots<i_k\leq n}\,\prod_{r=1}^s\,\mathbb{P}\left(\textstyle\bigcap_{j=1}^k\,A_{i_j}\right)\,.$$ Consequently, $$\displaystyle\text{Prob}(T)=\sum_{k=1}^n\,(-1)^{k-1}\,\sum_{1\leq i_1<i_2<\ldots<i_k\leq n}\,\Bigg(\mathbb{P}\left(\textstyle\bigcap_{j=1}^k\,A_{i_j}\right)\Bigg)^s\,.$$ This proves that $$0 \leq \sum_{k=1}^n\,(-1)^{k-1}\,\sum_{1\leq i_1<i_2<\ldots<i_k\leq n}\,\Bigg(\mathbb{P}\left(\textstyle\bigcap_{j=1}^k\,A_{i_j}\right)\Bigg)^s \leq 1\,.$$
In fact, if we have $A_i^r\in\mathcal{F}$ for $i=1,2,\ldots,n$ and $r=1,2,\ldots,s$, then $$\displaystyle0\leq\sum_{k=1}^n\,(-1)^{k-1}\,\sum_{1\leq i_1<i_2<\ldots<i_k\leq n}\,\prod_{r=1}^s\,\mathbb{P}\left(\textstyle\bigcap_{j=1}^k\,A^r_{i_j}\right)\leq 1\,.$$
• How are $X_r$ and Prob constructed? – simonzack Jul 10 '15 at 23:16
• Simple, equip $\Omega^s$ with the product $\sigma$-algebra on $\Omega$, and define $X_r:\Omega^s\to\Omega$ to be the canonical projection onto the $r$-th coordinate. The probability function $\text{Prob}$ is inherited from the probability measure $\mathbb{P}$ on $\Omega$. – Batominovski Jul 10 '15 at 23:28