Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


share|cite|improve this question
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. – Dilip Sarwate Jan 23 '12 at 22:22

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

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.