Inclusion-Exclusion Principle (Probability) - Bonferroni inequalities

[icystrike]

Homework Statement

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.

Thanks in advanced :)

 

[Ray Vickson]

Homework Statement

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:

Attachment ​

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.

Thanks in advanced :)

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.

 

[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

 

[Ray Vickson]

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

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

 

[icystrike]

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

 

[Ray Vickson]

Homework Statement

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.

Thanks in advanced :)

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

 

[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})