1
$\begingroup$

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.

  • 1
    Is there any reason for considering $2^n-n$ events $E_i$ rather than $n$ events which would simplify the notation? That is, do the $E_i$ have more specific meaning that you are not revealing to us? For example, ignoring a possible typographical error in the upper limit, you _could_ actually be wanting to find the probability that two or more of $n$ events have occurred.2012-01-23

2 Answers 2

3

$$\eqalign{ P\Bigl(\bigcup_{i=1}^n E_i\Bigr) = \sum_{i\le n} P(E_i) - &\sum_{i_1

The subscripts in the above sums are just a handy way to write, for example in the term $\sum\limits_{i_1, "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$).

3

$\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) $