Proof of a probability inequality

In summary, the problem asks to prove the inequality P(\bigcup_{i=1}^\infty A_i) \le \sum_{i=1}^\infty P(A_i) for a probability measure P(ω). The solution uses the induction method, starting with the base case and then assuming the inequality holds for n sets, and proving it for n+1 sets. The solution also uses the fact that if there are shared elements in any of the sets, their intersection is not empty and some elements will be "counted twice." The solution could be made more efficient by using the inclusion-exclusion principle or expressing the union as disjoint sets and using the countable additive axiom.
  • #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.
 
Physics news on Phys.org
  • #2
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.
 
Last edited:
  • #3
Jyan said:

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.

It would have been much more efficient to use the inclusion-exclusion principle at the start:
[tex] 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).[/tex]
 
  • #4
MarneMath said:
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.
 
  • #5
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.
 
  • #6
MarneMath said:
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:

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

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,

[tex] \bigcap_{i=1}^{\infty}B_i = \emptyset [/tex]

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

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

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

FAQ: Proof of a probability inequality

1. What is "Proof of a probability inequality"?

"Proof of a probability inequality" refers to a mathematical demonstration that a certain probability relationship or inequality holds true. This is often used in statistics and probability theory to show the likelihood of certain events occurring.

2. Why is "Proof of a probability inequality" important?

Having a solid proof of a probability inequality is crucial in ensuring the accuracy and validity of statistical and probability calculations. It allows for a better understanding of the likelihood of certain events and can be used to make informed decisions.

3. How is "Proof of a probability inequality" different from a regular proof?

The main difference between a "Proof of a probability inequality" and a regular proof is that the former involves probabilities and statistical concepts, while the latter is a more general mathematical argument. In a "Proof of a probability inequality", the goal is to show that a certain inequality or relationship holds true for a specific probability distribution or event.

4. What types of probability inequalities can be proven?

Probability inequalities can range from simple relationships between two probabilities (e.g. P(A) < P(B)) to more complex inequalities involving multiple events and probability distributions. Some common examples include Markov's inequality, Chebyshev's inequality, and the Central Limit Theorem.

5. What is the process for proving a probability inequality?

The process for proving a probability inequality involves utilizing mathematical techniques such as algebra, calculus, and probability theory to manipulate and simplify the given probabilities or events. The goal is to show that the inequality holds true for all possible values of the variables involved, using logical reasoning and mathematical principles.

Similar threads

Back
Top