# Inclusion-Exclusion Principle (Probability) - Bonferroni inequalities

1. Mar 10, 2013

### icystrike

1. The problem statement, all variables and given/known data

Hi PF! I am studying from a book - A first course in probability by Sheldon Ross, and I have came across this section whereby the are trying to prove the upper bound (equations 4.1 and 4.3) and lower bound (equation 4.2) of the inclusion-exclusion principle from basic probability. The section has been attached below:

However, I have not clearly understood two parts that have been stated in the attachment. The two parts are stated below;

1) They have mentioned "fixing $i$ " twice in the book, and what do they mean by that? I don't see the need for me to fix any "variable".

2) How can they simply get $P(U_{j<i} E_{i}E_{j}) \geq \sum_{j<i}P(E_{i}E_{j}) - \sum_{k<j<i} P(E_{i}E_{j}E_{i}E_{k})$ from (4.2)? What are the considerations that have to be made? My concern is towards the $P(E_{i}E_{j}E_{i}E_{k})$ of the equation.

#### Attached Files:

• ###### photo (1).jpg
File size:
39.2 KB
Views:
122
Last edited: Mar 10, 2013
2. Mar 10, 2013

### Ray Vickson

There are numerous editions of Ross' books, and different editions have different numbers of chapters, sections, etc. I have two of his books remaining (after retiring and downsizing) but cannot find the information you speak of in either book. Please just write out here the actual material that is causing you problems.

3. Mar 10, 2013

### icystrike

Hi Ray!

Thank you for your reply. I have actually attached the cited material as attachment in my previous post. Please let me know if you are able to access the "jpeg" file.

With regards

4. Mar 10, 2013

### Ray Vickson

In my browser the attachments do not appear; are you sure you followed PF instructions about including attachements?

5. Mar 10, 2013

### icystrike

My apologies, I have updated the link again. Please refer to the first post again :)

6. Mar 10, 2013

### Ray Vickson

For (2): say we have $E_1E_2 \cup E_1E_3 \cup E_2E_3.$ Let $A_1 = E_1E_2,\, A_2 = E_1 E_3,\, A_3 = E_2 E_3.$ Now apply the inequality $$P(A_1 \cup A_2 \cup A_3) \geq \sum_l P(A_l) - \sum_{l < m} P(A_l A_m).$$

7. Mar 11, 2013

### icystrike

Thanks Ray!

Do you mean that I can define $A_{i}=E_{i}E_{j}$ such that $j<i$ and likewise, $A_{j}=E_{j}E_{k}$ such that $k<j$.

Hence, $P(\bigcup_{i=1}^{n} A_{i}) \geq \sum_{i=1}^{n} P(A_{i}) - \sum_{j<i} P(A_{i}A_{j})$

$P(\bigcup_{j<i}^{n} E_{i}E_{j}) \geq \sum_{j<i} P(E_{i}E_{j}) - \sum_{k<j<i} P(E_{i}E_{j}E_{j}E_{k})$

$P(\bigcup_{j<i}^{n} E_{i}E_{j}) \geq \sum_{j<i} P(E_{i}E_{j}) - \sum_{k<j<i} P(E_{i}E_{j}E_{k})$

Last edited: Mar 11, 2013