Proof of a probability inequality

[Jyan]

Homework Statement

I'm working on some MIT OCW (http://ocw.mit.edu/courses/electric...y-fall-2008/assignments/MIT6_436JF08_hw01.pdf). I've attempted problem #5, just looking for some comments on the quality / validity of my proof.

Homework Equations

Show: $$P(\bigcup_{i=1}^\infty A_i) \le \sum_{i=1}^\infty P(A_i)$$

Where P(ω) is a probability measure for the event ω.

The Attempt at a Solution

The intuition is that if there are shared elements in any of the sets (their intersection is not empty) then some stuff will be "counted twice".

I prove this by induction, starting with the base case:

$$P(A_1 \cup A_2) \le P(A_1) + P(A_2)$$ Proof:
$$Let \space B = A_1 \cap A_2$$ Then,
$$A_1 \cup A_2 = (A_1 \setminus B) \cup (A_2 \setminus B) \cup B$$
Since $$(A_1 \setminus B) \cap (A_2 \setminus B) \cap B = \emptyset$$
$$P(A_1 \cup A_2) = P(A_1 \setminus B) + P(A_2 \setminus B) + P(B)$$

We also have
$$P(A_1) = P(A_1 \setminus B) + P(B)$$ And,
$$P(A_2) = P(A_2 \setminus B) + P(B)$$
Therefore,
$$P(A_1) + P(A_2) = P(A_1 \setminus B) + P(A_2 \setminus B) + 2P(B) \ge P(A_1 \cup A_2)$$
Which proves the base case for induction.

Now assume

$$P(\bigcup_{i=1}^n) \le \sum_{i=1}^nP(A_i)$$

Using the base case,

$$P((\bigcup_{i=1}^n A_i) \cup A_{n+1}) \le \sum_{i=1}^nP(A_i) + P(A_{n+1})$$

$$\therefore P(\bigcup_{i=1}^{n+1}A_i) \le \sum_{i=1}^{n+1}P(A_i)$$

The result follows by induction QED.

 

[MarneMath]

If you want to use the hint there are a few ways you can do this. I'm not entire convinced by your method though. I would prefer to see the disjoint sets written with n terms (eg B_1 = A_1 and B_n =A_n\ Union of A_i from i = 1 to n.) Then mention the pairwise disjoint collection. From there it should more or less follow from the additive axiom.

As a side note, if you know measure theory, then the inequality naturally follows since the measure is sigma sub-additive. I only mention this since the problem mentions it is a measure.

 

[Ray Vickson]

Homework Statement

I'm working on some MIT OCW (http://ocw.mit.edu/courses/electric...y-fall-2008/assignments/MIT6_436JF08_hw01.pdf). I've attempted problem #5, just looking for some comments on the quality / validity of my proof.

Homework Equations

Show: $$P(\bigcup_{i=1}^\infty A_i) \le \sum_{i=1}^\infty P(A_i)$$

Where P(ω) is a probability measure for the event ω.

The Attempt at a Solution

The intuition is that if there are shared elements in any of the sets (their intersection is not empty) then some stuff will be "counted twice".

I prove this by induction, starting with the base case:

$$P(A_1 \cup A_2) \le P(A_1) + P(A_2)$$ Proof:
$$Let \space B = A_1 \cap A_2$$ Then,
$$A_1 \cup A_2 = (A_1 \setminus B) \cup (A_2 \setminus B) \cup B$$
Since $$(A_1 \setminus B) \cap (A_2 \setminus B) \cap B = \emptyset$$
$$P(A_1 \cup A_2) = P(A_1 \setminus B) + P(A_2 \setminus B) + P(B)$$

We also have
$$P(A_1) = P(A_1 \setminus B) + P(B)$$ And,
$$P(A_2) = P(A_2 \setminus B) + P(B)$$
Therefore,
$$P(A_1) + P(A_2) = P(A_1 \setminus B) + P(A_2 \setminus B) + 2P(B) \ge P(A_1 \cup A_2)$$
Which proves the base case for induction.

Now assume

$$P(\bigcup_{i=1}^n) \le \sum_{i=1}^nP(A_i)$$

Using the base case,

$$P((\bigcup_{i=1}^n A_i) \cup A_{n+1}) \le \sum_{i=1}^nP(A_i) + P(A_{n+1})$$

$$\therefore P(\bigcup_{i=1}^{n+1}A_i) \le \sum_{i=1}^{n+1}P(A_i)$$

The result follows by induction QED.

It would have been much more efficient to use the inclusion-exclusion principle at the start:
$$P(A_1 \cup A_2) = P(A_1) + P(A_2) - P(A_1 \cap A_2) \leq P(A_1) + P(A_2).$$

 

[Jyan]

If you want to use the hint there are a few ways you can do this. I'm not entire convinced by your method though. I would prefer to see the disjoint sets written with n terms (eg B_1 = A_1 and B_n =A_n\ Union of A_i from i = 1 to n.) Then mention the pairwise disjoint collection. From there it should more or less follow from the additive axiom.

As a side note, if you know measure theory, then the inequality naturally follows since the measure is sigma sub-additive. I only mention this since the problem mentions it is a measure.

Can you elaborate a little more? I'm not sure I understand. Is there something wrong with my logic?

Also, I did not use the inclusion-exlusion principle because I have not seen or written a proof for it yet.

 

[MarneMath]

I'm not saying your logic is wrong or method wrong if a bit tedious. I'm simply saying that if I was grading this, I wouldn't be convinced that the student really knew all the details and unstated assumptions going on or just hoping to get by. That is where my uneasiness comes from. I think as a student doing an assignment, even for self-learning, you should put more detail into your work and make it more clear. Anyone can write, "it follows from such and such." but without justification, I really can't comment on if you are making said leap with true comprehension.

As for my comment earlier. I was remarking on how the hint in the problem suggest you express the union as disjoint sets. If you want to do this, one natural way be to set B_1 = A_1 and inductively define the B_n as
B_n = A_n\U(A_i, i = 1 to n - 1), for n > 1. From there you should notice a certain fact about B_1, B_2, ... and how the union of B_i relate to the union of A_i. The goal here is to be able to force the use of countable additive axiom (usually the third axiom listed) and the increase property.

That's the method the hint in the problem is aiming at getting you to do.

 

[Jyan]

I'm not saying your logic is wrong or method wrong if a bit tedious. I'm simply saying that if I was grading this, I wouldn't be convinced that the student really knew all the details and unstated assumptions going on or just hoping to get by. That is where my uneasiness comes from. I think as a student doing an assignment, even for self-learning, you should put more detail into your work and make it more clear. Anyone can write, "it follows from such and such." but without justification, I really can't comment on if you are making said leap with true comprehension.

As for my comment earlier. I was remarking on how the hint in the problem suggest you express the union as disjoint sets. If you want to do this, one natural way be to set B_1 = A_1 and inductively define the B_n as
B_n = A_n\U(A_i, i = 1 to n - 1), for n > 1. From there you should notice a certain fact about B_1, B_2, ... and how the union of B_i relate to the union of A_i. The goal here is to be able to force the use of countable additive axiom (usually the third axiom listed) and the increase property.

That's the method the hint in the problem is aiming at getting you to do.

Ah I See. I actually did leave out a few steps in my proof just because writing out in latex is tedious and proofs I read in books seem like they leave out the same kind of stuff I did, but I guess I should be as explicit as possible.

As for applying the hint, this is what I have:

$$B_1 = A_1$$
Through induction, define B_i for all i in N
$$B_i = A_i \setminus (\bigcup_{i=1}^{i-1}A_i)$$

Since B_i is A_i with a set difference, each B_i is a subset (not a strict one though) of A_i, which means that P(B_i) <= P(A_i). Moreover, the union of all the Bs is equal to the union of all the As since repeated elements are not included in the union. (is there a better way to express this?)

Moreoever, each B_i removes all common elements with B_(i-1), B_(i-2), ... Therefore,

$$\bigcap_{i=1}^{\infty}B_i = \emptyset$$

So,

Because the union of the Bs is equal to the union of the As (first equality), the Bs are disjoint (second equality), and each B_i is a subset of A_i (the inequality):

$$P(\bigcup_{i=1}^{\infty} A_i) = P(\bigcup_{i=1}^\infty B_i) = \sum_{i=1}^{\infty} P(B_i) \le \sum_{i=1}^{\infty}P(A_i)$$

I appreciate the help/comments from everyone, thank you!