- #1

Jyan

- 36

- 2

## 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: [tex] P(\bigcup_{i=1}^\infty A_i) \le \sum_{i=1}^\infty P(A_i) [/tex]

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:

[tex] P(A_1 \cup A_2) \le P(A_1) + P(A_2) [/tex] Proof:

[tex] Let \space B = A_1 \cap A_2 [/tex] Then,

[tex] A_1 \cup A_2 = (A_1 \setminus B) \cup (A_2 \setminus B) \cup B [/tex]

Since [tex] (A_1 \setminus B) \cap (A_2 \setminus B) \cap B = \emptyset [/tex]

[tex] P(A_1 \cup A_2) = P(A_1 \setminus B) + P(A_2 \setminus B) + P(B) [/tex]

We also have

[tex] P(A_1) = P(A_1 \setminus B) + P(B) [/tex] And,

[tex] P(A_2) = P(A_2 \setminus B) + P(B) [/tex]

Therefore,

[tex] 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) [/tex]

Which proves the base case for induction.

Now assume

[tex] P(\bigcup_{i=1}^n) \le \sum_{i=1}^nP(A_i) [/tex]

Using the base case,

[tex] P((\bigcup_{i=1}^n A_i) \cup A_{n+1}) \le \sum_{i=1}^nP(A_i) + P(A_{n+1}) [/tex]

[tex] \therefore P(\bigcup_{i=1}^{n+1}A_i) \le \sum_{i=1}^{n+1}P(A_i) [/tex]

The result follows by induction QED.