Inclusion-exclusion principle question

Question

1st part of my question:

I have that $$P\left(\bigcup_{i=1}^{{2^n-n}}E_i\right)$$ , how would I write it out using the inclusion-exclusion principle? I know it starts off: $$\sum_{i=1}^{2^n-n} P(E_i)+...$$ But after that Im not sure what goes next.

2nd part --- I also read somewhere that (by subadditivity), $P\left(\bigcup_{i=1}^{{2^n-n}}E_i\right) \le \sum_{i=1}^{2^n-n} P(E_i)$, but why is that the case? I dont understand how it by subadditivity the above inequality comes about.

Thanks.

Answer 1

$$\eqalign{ P\Bigl(\bigcup_{i=1}^n E_i\Bigr) = \sum_{i\le n} P(E_i) - &\sum_{i_1<i_2}\underbrace{ P(E_{i_1}\cap E_{i_2})}_{ {\text {two at a time}}} +\sum_{i_1<i_2<i_3} \underbrace{ P(E_{i_1}\cap E_{i_2}\cap E_{i_3})}_{\text {three at a time}} - \cr &\cdots+ (-1)^{n}\sum_{i_1<i_2<\cdots<i_{n-1} } \underbrace{ P(E_{i_1}\cap\cdots\cap E_{i_{n-1}} )}_{(n-1)\text { at a time}} \cr &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ + (-1)^{n+1}P(E_1\cap E_2\cap\cdots\cap E_n)} $$

The subscripts in the above sums are just a handy way to write, for example in the term $\sum\limits_{i_1<i_2} P(E_{i_1}\cap E_{i_2}) $, "take the sum of the probabilities of intersections of two distinct events (the intersections taken without regard to order; that is, in the sum, you have only only one of, e.g., $P(E_1\cap E_2)$ or $P(E_2\cap E_1) \thinspace $)".

Of course my "$n$" is your "$2^n-n$".

For your concern at the end of your post, note the formula above has negative terms.

In general, if the events $\{E_i\}$ are mutually exclusive, then $P(\cup E_i )=\sum P(E_i)$; but if the events overlap then $P(\cup E_i )\le\sum P(E_i)$. This is because the right hand side of the preceeding formula counts some probabilities more than once (namely those in the intersection of overlapping $E_i$).

Answer 2

$$\sum_{i=1}^{2^n-n} P(E_i) - \sum_{i=2}^{2^n-n} \sum_{j=1}^{i-1} P(E_i \cap E_j) + \sum_{i=3}^{2^n-n} \sum_{j=2}^{i-1} \sum_{k=1}^{j-1} P(E_i \cap E_j\cap E_k) -\cdots$$

The key point about the limits of the sums is you want each possible combination once and the $i,j,k,\ldots$ distinct

For the second part you have

$$ P\left(\bigcup_{i=1}^{{2^n-n}}E_i\right) = P(E_1)+P(E_2 \cap E_1^C)+ P(E_3 \cap E_2^C \cap E_1^C) + \cdots$$

$$\le P(E_1)+P(E_2)+ P( E_3) + \cdots = \sum_{i=1}^{2^n-n} P(E_i) $$