Inclusion–exclusion principle for probability

135 Views Asked by At

Inclusion–exclusion principle for probability is as follows: https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle

(1)How to use this principle to show that: $$\sum_{i=1}^nP(\{x_i\}\subset X)+\sum_{1\leq i_1<i_2\leq n}P(\{x_{i_1}, x_{i_2}\}\subset X)+\dots+(-1)^{n-1}\sum_{i=1}^nP(\{x_1, x_2, \dots, x_n\}\subset X)=?$$

(2)Also, What is the $1-P(\{x_1,\dots, x_n\}\subset X^c)?$

EDIT: What I want is that why $$1-\sum_{i=1}^nP(\{x_i\}\subset X)+\sum_{1\leq i_1<i_2\leq n}P(\{x_{i_1}, x_{i_2}\}\subset X)+\dots+(-1)^{n}\sum_{i=1}^n P(\{x_1, x_2, \dots, x_n\}\subset X)=P(X\subset \Omega\setminus \{x_1,\dots, x_n\})$$ where $X=\{x_1, \dots, x_N\}$ of a finite set $\Omega$ with $|\Omega|\geq N$

1

There are 1 best solutions below

5
On BEST ANSWER

The statement doesn't look right..It should read:

$1-P(${$x_1,...,x_n$}$\subset X^c)=\sum_k P${$x_k$}$\subset X)-\sum_{k\lt j}P(${$x_k,x_j$}$\subset X)+$etc.

The basic idea is the probability that all the subsets are in $X^C$ is $1-$ the probability that at least one subset is in $X$. To calculate the later you add up the probabilities of one subset in $X$, but you need to subtract the probabilities that a pair of subsets is in $X$. This results from a basic relation $P(A\cup B)=P(A)+P(B)-P(A\cap B)$

You then need to add back the probabilities for three subsets in $X$,etc.