Mixing
Could someone explain Boole's inequality proof to me?
$begingroup$
I am currently writing a report about George Boole and need help understanding this proof, any help would be appreciated.
Thank you mathematicians.
probability-theory
asked Jan 29 at 15:13
M. ClayM. Clay
104
$endgroup$
add a comment |
$begingroup$
I am currently writing a report about George Boole and need help understanding this proof, any help would be appreciated.
Thank you mathematicians.
probability-theory
asked Jan 29 at 15:13
M. ClayM. Clay
104
$endgroup$
1
$begingroup$
What proof? What part don't you understand? I can copy and paste the proof from Wikipedia (en.wikipedia.org/wiki/Boole%27s_inequality) into an answer, but that won't really help you unless you tell us which part you don't get.
$endgroup$
– kccu
Jan 29 at 15:17
$begingroup$
The proof without induction.
$endgroup$
– M. Clay
Jan 29 at 15:18
1
$begingroup$
Again, what part of it are you having trouble with?
$endgroup$
– kccu
Jan 29 at 15:21
$begingroup$
When the sets get modified.
$endgroup$
– M. Clay
Jan 29 at 15:22
add a comment |
$begingroup$
I am currently writing a report about George Boole and need help understanding this proof, any help would be appreciated.
Thank you mathematicians.
probability-theory
asked Jan 29 at 15:13
M. ClayM. Clay
104
$endgroup$
I am currently writing a report about George Boole and need help understanding this proof, any help would be appreciated.
Thank you mathematicians.
probability-theory
probability-theory
asked Jan 29 at 15:13
M. ClayM. Clay
104
asked Jan 29 at 15:13
M. ClayM. Clay
104
asked Jan 29 at 15:13
M. ClayM. Clay
104
asked Jan 29 at 15:13
M. ClayM. Clay
104
asked Jan 29 at 15:13
M. ClayM. Clay
104
104
1
$begingroup$
What proof? What part don't you understand? I can copy and paste the proof from Wikipedia (en.wikipedia.org/wiki/Boole%27s_inequality) into an answer, but that won't really help you unless you tell us which part you don't get.
$endgroup$
– kccu
Jan 29 at 15:17
$begingroup$
The proof without induction.
$endgroup$
– M. Clay
Jan 29 at 15:18
1
$begingroup$
Again, what part of it are you having trouble with?
$endgroup$
– kccu
Jan 29 at 15:21
$begingroup$
When the sets get modified.
$endgroup$
– M. Clay
Jan 29 at 15:22
add a comment |
1
$begingroup$
What proof? What part don't you understand? I can copy and paste the proof from Wikipedia (en.wikipedia.org/wiki/Boole%27s_inequality) into an answer, but that won't really help you unless you tell us which part you don't get.
$endgroup$
– kccu
Jan 29 at 15:17
$begingroup$
The proof without induction.
$endgroup$
– M. Clay
Jan 29 at 15:18
1
$begingroup$
Again, what part of it are you having trouble with?
$endgroup$
– kccu
Jan 29 at 15:21
$begingroup$
When the sets get modified.
$endgroup$
– M. Clay
Jan 29 at 15:22
1
1
$begingroup$
What proof? What part don't you understand? I can copy and paste the proof from Wikipedia (en.wikipedia.org/wiki/Boole%27s_inequality) into an answer, but that won't really help you unless you tell us which part you don't get.
$endgroup$
– kccu
Jan 29 at 15:17
$begingroup$
What proof? What part don't you understand? I can copy and paste the proof from Wikipedia (en.wikipedia.org/wiki/Boole%27s_inequality) into an answer, but that won't really help you unless you tell us which part you don't get.
$endgroup$
– kccu
Jan 29 at 15:17
$begingroup$
The proof without induction.
$endgroup$
– M. Clay
Jan 29 at 15:18
$begingroup$
The proof without induction.
$endgroup$
– M. Clay
Jan 29 at 15:18
1
1
$begingroup$
Again, what part of it are you having trouble with?
$endgroup$
– kccu
Jan 29 at 15:21
$begingroup$
Again, what part of it are you having trouble with?
$endgroup$
– kccu
Jan 29 at 15:21
$begingroup$
When the sets get modified.
$endgroup$
– M. Clay
Jan 29 at 15:22
$begingroup$
When the sets get modified.
$endgroup$
– M. Clay
Jan 29 at 15:22
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Boole's inequality states that for any events $A_1,A_2,dots$,
$$mathbb{P}left(bigcup_{i=1}^infty A_iright ) leq sum_{i=1}^infty mathbb{P}(A_i).$$
The proof makes use of the fact that for any disjoint events $B_1,B_2,dots$,
$$mathbb{P}left(bigcup_{i=1}^n B_iright) = sum_{i=1}^infty mathbb{P}(B_i).$$
How does this help? If we can find a sequence of events $B_1,B_2,dots$ such that all of the following hold:
$B_1,B_2,dots$ are disjoint- $bigcup_{i=1}^infty A_i = bigcup_{i=1}^infty B_i$
- For all $i$, $mathbb{P}(B_i) leq mathbb{P}(A_i)$,
then we would have
$$mathbb{P}left(bigcup_{i=1}^infty A_iright )=mathbb{P}left(bigcup_{i=1}^infty B_iright )= sum_{i=1}^infty mathbb{P}(B_i) leq sum_{i=1}^infty mathbb{P}(A_i).$$
(The first equality is from bullet point two, the second equality is from bullet point one, and the inequality is from bullet point three.)
The idea is that we can turn the $A_i$ into disjoint sets by "cutting away" the parts of the $A_i$ that overlap with the other sets. To do this in a systematic way, we define
begin{align*}
B_1 &= A_1\
B_2 &= A_2 - A_1\
B_3 &= A_3 - (A_1 cup A_2)\
B_4 &= A_4 - (A_1 cup A_2 cup A_3)\
&vdots\
B_i &= A_i - bigcup_{j=1}^{i-1}A_j\
&vdots
end{align*}
Clearly each $B_isubseteq A_i$, since we obtain $B_i$ by taking $A_i$ and "cutting away" some part of it. So $mathbb{P}(B_i) leq mathbb{P}(A_i)$. So we have satisfied the third bullet point above.
The fact that $B_i subseteq A_i$ for all $i$ also implies that the union of the $B_i$ is contained in the union of the $A_i$: $bigcup_{i=1}^infty B_i subseteq bigcup_{i=1}^infty A_i$. This is half of the second bullet point above. The other half requires showing that $bigcup_{i=1}^infty A_i subseteq bigcup_{i=1}^infty B_i$. If $x in bigcup_{i=1}^infty A_i$, then $x in A_i$ for some $i$, or possibly more than one $i$. For instance, maybe $x$ is in $A_3$, $A_4$, and $A_6$ (and none of the others). How do we know which $B_i$ it is in? By definition, $B_4$ does not contain any of the elements in $A_3$, as they are cut away. Similarly, $B_6$ does not contain any of the elements in $A_3$. So $x$ cannot be in $B_4$ or $B_6$. $B_3$ contains all the elements of $A_3$ that aren't also in $A_1$ or $A_2$. Since $x$ is not in $A_1$ or $A_2$, it doesn't get "cut away" from $A_3$ when we define $B_3$. Hence $x in B_3$. In general, if we know $x in A_{i_1},A_{i_2},dots$ where $i_1<i_2<cdots$, then we know $x in B_{i_1}$.
Finally, we need to show that $B_1,B_2,dots$ are disjoint, i.e., for any $i neq j$, $B_i cap B_j = emptyset$. Suppose $i neq j$, and without loss of generality we can assume $i<j$ (otherwise just re-name the indices so that this is true). Then $B_j$ is defined by taking $A_j$ and removing all of the elements of $A_1,A_2,dots,A_{j-1}$. In particular, since $i<j$, all of the elements of $A_i$ are removed from $B_j$. And since $B_i subseteq A_i$, we know all of the elements of $B_i$ are removed from $B_j$. So they have to be disjoint. If you want to prove this symbolically, we have
begin{align*}
B_i cap B_j &subseteq A_i cap left(A_j - bigcup_{k=1}^{j-1}A_kright)\
&=A_i cap left(A_j cap left(bigcup_{k=1}^{j-1} A_kright)^c right)\
&= A_i capleft(A_j cap left(bigcap_{k=1}^{j-1}A_k^cright)right)\
&subseteq A_i cap A_i^c=emptyset.
end{align*}
So $B_i cap B_j subseteq emptyset$, which implies $B_i cap B_j = emptyset$.
Now we have verified all three bullet points, so the inequality follows.
answered Jan 29 at 15:45
kccukccu
10.8k11229
$endgroup$
$begingroup$
Thank you very much, this was extremely helpful.
$endgroup$
– M. Clay
Jan 29 at 16:20
$begingroup$
If your question has been answered, you can click the checkmark next to my answer to accept it.
$endgroup$
– kccu
Jan 29 at 18:52
add a comment |
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3092293%2fcould-someone-explain-booles-inequality-proof-to-me%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Boole's inequality states that for any events $A_1,A_2,dots$,
$$mathbb{P}left(bigcup_{i=1}^infty A_iright ) leq sum_{i=1}^infty mathbb{P}(A_i).$$
The proof makes use of the fact that for any disjoint events $B_1,B_2,dots$,
$$mathbb{P}left(bigcup_{i=1}^n B_iright) = sum_{i=1}^infty mathbb{P}(B_i).$$
How does this help? If we can find a sequence of events $B_1,B_2,dots$ such that all of the following hold:
$B_1,B_2,dots$ are disjoint- $bigcup_{i=1}^infty A_i = bigcup_{i=1}^infty B_i$
- For all $i$, $mathbb{P}(B_i) leq mathbb{P}(A_i)$,
then we would have
$$mathbb{P}left(bigcup_{i=1}^infty A_iright )=mathbb{P}left(bigcup_{i=1}^infty B_iright )= sum_{i=1}^infty mathbb{P}(B_i) leq sum_{i=1}^infty mathbb{P}(A_i).$$
(The first equality is from bullet point two, the second equality is from bullet point one, and the inequality is from bullet point three.)
The idea is that we can turn the $A_i$ into disjoint sets by "cutting away" the parts of the $A_i$ that overlap with the other sets. To do this in a systematic way, we define
begin{align*}
B_1 &= A_1\
B_2 &= A_2 - A_1\
B_3 &= A_3 - (A_1 cup A_2)\
B_4 &= A_4 - (A_1 cup A_2 cup A_3)\
&vdots\
B_i &= A_i - bigcup_{j=1}^{i-1}A_j\
&vdots
end{align*}
Clearly each $B_isubseteq A_i$, since we obtain $B_i$ by taking $A_i$ and "cutting away" some part of it. So $mathbb{P}(B_i) leq mathbb{P}(A_i)$. So we have satisfied the third bullet point above.
The fact that $B_i subseteq A_i$ for all $i$ also implies that the union of the $B_i$ is contained in the union of the $A_i$: $bigcup_{i=1}^infty B_i subseteq bigcup_{i=1}^infty A_i$. This is half of the second bullet point above. The other half requires showing that $bigcup_{i=1}^infty A_i subseteq bigcup_{i=1}^infty B_i$. If $x in bigcup_{i=1}^infty A_i$, then $x in A_i$ for some $i$, or possibly more than one $i$. For instance, maybe $x$ is in $A_3$, $A_4$, and $A_6$ (and none of the others). How do we know which $B_i$ it is in? By definition, $B_4$ does not contain any of the elements in $A_3$, as they are cut away. Similarly, $B_6$ does not contain any of the elements in $A_3$. So $x$ cannot be in $B_4$ or $B_6$. $B_3$ contains all the elements of $A_3$ that aren't also in $A_1$ or $A_2$. Since $x$ is not in $A_1$ or $A_2$, it doesn't get "cut away" from $A_3$ when we define $B_3$. Hence $x in B_3$. In general, if we know $x in A_{i_1},A_{i_2},dots$ where $i_1<i_2<cdots$, then we know $x in B_{i_1}$.
Finally, we need to show that $B_1,B_2,dots$ are disjoint, i.e., for any $i neq j$, $B_i cap B_j = emptyset$. Suppose $i neq j$, and without loss of generality we can assume $i<j$ (otherwise just re-name the indices so that this is true). Then $B_j$ is defined by taking $A_j$ and removing all of the elements of $A_1,A_2,dots,A_{j-1}$. In particular, since $i<j$, all of the elements of $A_i$ are removed from $B_j$. And since $B_i subseteq A_i$, we know all of the elements of $B_i$ are removed from $B_j$. So they have to be disjoint. If you want to prove this symbolically, we have
begin{align*}
B_i cap B_j &subseteq A_i cap left(A_j - bigcup_{k=1}^{j-1}A_kright)\
&=A_i cap left(A_j cap left(bigcup_{k=1}^{j-1} A_kright)^c right)\
&= A_i capleft(A_j cap left(bigcap_{k=1}^{j-1}A_k^cright)right)\
&subseteq A_i cap A_i^c=emptyset.
end{align*}
So $B_i cap B_j subseteq emptyset$, which implies $B_i cap B_j = emptyset$.
Now we have verified all three bullet points, so the inequality follows.
answered Jan 29 at 15:45
kccukccu
10.8k11229
$endgroup$
$begingroup$
Thank you very much, this was extremely helpful.
$endgroup$
– M. Clay
Jan 29 at 16:20
$begingroup$
If your question has been answered, you can click the checkmark next to my answer to accept it.
$endgroup$
– kccu
Jan 29 at 18:52
add a comment |
$begingroup$
Boole's inequality states that for any events $A_1,A_2,dots$,
$$mathbb{P}left(bigcup_{i=1}^infty A_iright ) leq sum_{i=1}^infty mathbb{P}(A_i).$$
The proof makes use of the fact that for any disjoint events $B_1,B_2,dots$,
$$mathbb{P}left(bigcup_{i=1}^n B_iright) = sum_{i=1}^infty mathbb{P}(B_i).$$
How does this help? If we can find a sequence of events $B_1,B_2,dots$ such that all of the following hold:
$B_1,B_2,dots$ are disjoint- $bigcup_{i=1}^infty A_i = bigcup_{i=1}^infty B_i$
- For all $i$, $mathbb{P}(B_i) leq mathbb{P}(A_i)$,
then we would have
$$mathbb{P}left(bigcup_{i=1}^infty A_iright )=mathbb{P}left(bigcup_{i=1}^infty B_iright )= sum_{i=1}^infty mathbb{P}(B_i) leq sum_{i=1}^infty mathbb{P}(A_i).$$
(The first equality is from bullet point two, the second equality is from bullet point one, and the inequality is from bullet point three.)
The idea is that we can turn the $A_i$ into disjoint sets by "cutting away" the parts of the $A_i$ that overlap with the other sets. To do this in a systematic way, we define
begin{align*}
B_1 &= A_1\
B_2 &= A_2 - A_1\
B_3 &= A_3 - (A_1 cup A_2)\
B_4 &= A_4 - (A_1 cup A_2 cup A_3)\
&vdots\
B_i &= A_i - bigcup_{j=1}^{i-1}A_j\
&vdots
end{align*}
Clearly each $B_isubseteq A_i$, since we obtain $B_i$ by taking $A_i$ and "cutting away" some part of it. So $mathbb{P}(B_i) leq mathbb{P}(A_i)$. So we have satisfied the third bullet point above.
The fact that $B_i subseteq A_i$ for all $i$ also implies that the union of the $B_i$ is contained in the union of the $A_i$: $bigcup_{i=1}^infty B_i subseteq bigcup_{i=1}^infty A_i$. This is half of the second bullet point above. The other half requires showing that $bigcup_{i=1}^infty A_i subseteq bigcup_{i=1}^infty B_i$. If $x in bigcup_{i=1}^infty A_i$, then $x in A_i$ for some $i$, or possibly more than one $i$. For instance, maybe $x$ is in $A_3$, $A_4$, and $A_6$ (and none of the others). How do we know which $B_i$ it is in? By definition, $B_4$ does not contain any of the elements in $A_3$, as they are cut away. Similarly, $B_6$ does not contain any of the elements in $A_3$. So $x$ cannot be in $B_4$ or $B_6$. $B_3$ contains all the elements of $A_3$ that aren't also in $A_1$ or $A_2$. Since $x$ is not in $A_1$ or $A_2$, it doesn't get "cut away" from $A_3$ when we define $B_3$. Hence $x in B_3$. In general, if we know $x in A_{i_1},A_{i_2},dots$ where $i_1<i_2<cdots$, then we know $x in B_{i_1}$.
Finally, we need to show that $B_1,B_2,dots$ are disjoint, i.e., for any $i neq j$, $B_i cap B_j = emptyset$. Suppose $i neq j$, and without loss of generality we can assume $i<j$ (otherwise just re-name the indices so that this is true). Then $B_j$ is defined by taking $A_j$ and removing all of the elements of $A_1,A_2,dots,A_{j-1}$. In particular, since $i<j$, all of the elements of $A_i$ are removed from $B_j$. And since $B_i subseteq A_i$, we know all of the elements of $B_i$ are removed from $B_j$. So they have to be disjoint. If you want to prove this symbolically, we have
begin{align*}
B_i cap B_j &subseteq A_i cap left(A_j - bigcup_{k=1}^{j-1}A_kright)\
&=A_i cap left(A_j cap left(bigcup_{k=1}^{j-1} A_kright)^c right)\
&= A_i capleft(A_j cap left(bigcap_{k=1}^{j-1}A_k^cright)right)\
&subseteq A_i cap A_i^c=emptyset.
end{align*}
So $B_i cap B_j subseteq emptyset$, which implies $B_i cap B_j = emptyset$.
Now we have verified all three bullet points, so the inequality follows.
answered Jan 29 at 15:45
kccukccu
10.8k11229
$endgroup$
$begingroup$
Thank you very much, this was extremely helpful.
$endgroup$
– M. Clay
Jan 29 at 16:20
$begingroup$
If your question has been answered, you can click the checkmark next to my answer to accept it.
$endgroup$
– kccu
Jan 29 at 18:52
add a comment |
$begingroup$
Boole's inequality states that for any events $A_1,A_2,dots$,
$$mathbb{P}left(bigcup_{i=1}^infty A_iright ) leq sum_{i=1}^infty mathbb{P}(A_i).$$
The proof makes use of the fact that for any disjoint events $B_1,B_2,dots$,
$$mathbb{P}left(bigcup_{i=1}^n B_iright) = sum_{i=1}^infty mathbb{P}(B_i).$$
How does this help? If we can find a sequence of events $B_1,B_2,dots$ such that all of the following hold:
$B_1,B_2,dots$ are disjoint- $bigcup_{i=1}^infty A_i = bigcup_{i=1}^infty B_i$
- For all $i$, $mathbb{P}(B_i) leq mathbb{P}(A_i)$,
then we would have
$$mathbb{P}left(bigcup_{i=1}^infty A_iright )=mathbb{P}left(bigcup_{i=1}^infty B_iright )= sum_{i=1}^infty mathbb{P}(B_i) leq sum_{i=1}^infty mathbb{P}(A_i).$$
(The first equality is from bullet point two, the second equality is from bullet point one, and the inequality is from bullet point three.)
The idea is that we can turn the $A_i$ into disjoint sets by "cutting away" the parts of the $A_i$ that overlap with the other sets. To do this in a systematic way, we define
begin{align*}
B_1 &= A_1\
B_2 &= A_2 - A_1\
B_3 &= A_3 - (A_1 cup A_2)\
B_4 &= A_4 - (A_1 cup A_2 cup A_3)\
&vdots\
B_i &= A_i - bigcup_{j=1}^{i-1}A_j\
&vdots
end{align*}
Clearly each $B_isubseteq A_i$, since we obtain $B_i$ by taking $A_i$ and "cutting away" some part of it. So $mathbb{P}(B_i) leq mathbb{P}(A_i)$. So we have satisfied the third bullet point above.
The fact that $B_i subseteq A_i$ for all $i$ also implies that the union of the $B_i$ is contained in the union of the $A_i$: $bigcup_{i=1}^infty B_i subseteq bigcup_{i=1}^infty A_i$. This is half of the second bullet point above. The other half requires showing that $bigcup_{i=1}^infty A_i subseteq bigcup_{i=1}^infty B_i$. If $x in bigcup_{i=1}^infty A_i$, then $x in A_i$ for some $i$, or possibly more than one $i$. For instance, maybe $x$ is in $A_3$, $A_4$, and $A_6$ (and none of the others). How do we know which $B_i$ it is in? By definition, $B_4$ does not contain any of the elements in $A_3$, as they are cut away. Similarly, $B_6$ does not contain any of the elements in $A_3$. So $x$ cannot be in $B_4$ or $B_6$. $B_3$ contains all the elements of $A_3$ that aren't also in $A_1$ or $A_2$. Since $x$ is not in $A_1$ or $A_2$, it doesn't get "cut away" from $A_3$ when we define $B_3$. Hence $x in B_3$. In general, if we know $x in A_{i_1},A_{i_2},dots$ where $i_1<i_2<cdots$, then we know $x in B_{i_1}$.
Finally, we need to show that $B_1,B_2,dots$ are disjoint, i.e., for any $i neq j$, $B_i cap B_j = emptyset$. Suppose $i neq j$, and without loss of generality we can assume $i<j$ (otherwise just re-name the indices so that this is true). Then $B_j$ is defined by taking $A_j$ and removing all of the elements of $A_1,A_2,dots,A_{j-1}$. In particular, since $i<j$, all of the elements of $A_i$ are removed from $B_j$. And since $B_i subseteq A_i$, we know all of the elements of $B_i$ are removed from $B_j$. So they have to be disjoint. If you want to prove this symbolically, we have
begin{align*}
B_i cap B_j &subseteq A_i cap left(A_j - bigcup_{k=1}^{j-1}A_kright)\
&=A_i cap left(A_j cap left(bigcup_{k=1}^{j-1} A_kright)^c right)\
&= A_i capleft(A_j cap left(bigcap_{k=1}^{j-1}A_k^cright)right)\
&subseteq A_i cap A_i^c=emptyset.
end{align*}
So $B_i cap B_j subseteq emptyset$, which implies $B_i cap B_j = emptyset$.
Now we have verified all three bullet points, so the inequality follows.
answered Jan 29 at 15:45
kccukccu
10.8k11229
$endgroup$
Boole's inequality states that for any events $A_1,A_2,dots$,
$$mathbb{P}left(bigcup_{i=1}^infty A_iright ) leq sum_{i=1}^infty mathbb{P}(A_i).$$
The proof makes use of the fact that for any disjoint events $B_1,B_2,dots$,
$$mathbb{P}left(bigcup_{i=1}^n B_iright) = sum_{i=1}^infty mathbb{P}(B_i).$$
How does this help? If we can find a sequence of events $B_1,B_2,dots$ such that all of the following hold:
$B_1,B_2,dots$ are disjoint- $bigcup_{i=1}^infty A_i = bigcup_{i=1}^infty B_i$
- For all $i$, $mathbb{P}(B_i) leq mathbb{P}(A_i)$,
then we would have
$$mathbb{P}left(bigcup_{i=1}^infty A_iright )=mathbb{P}left(bigcup_{i=1}^infty B_iright )= sum_{i=1}^infty mathbb{P}(B_i) leq sum_{i=1}^infty mathbb{P}(A_i).$$
(The first equality is from bullet point two, the second equality is from bullet point one, and the inequality is from bullet point three.)
The idea is that we can turn the $A_i$ into disjoint sets by "cutting away" the parts of the $A_i$ that overlap with the other sets. To do this in a systematic way, we define
begin{align*}
B_1 &= A_1\
B_2 &= A_2 - A_1\
B_3 &= A_3 - (A_1 cup A_2)\
B_4 &= A_4 - (A_1 cup A_2 cup A_3)\
&vdots\
B_i &= A_i - bigcup_{j=1}^{i-1}A_j\
&vdots
end{align*}
Clearly each $B_isubseteq A_i$, since we obtain $B_i$ by taking $A_i$ and "cutting away" some part of it. So $mathbb{P}(B_i) leq mathbb{P}(A_i)$. So we have satisfied the third bullet point above.
The fact that $B_i subseteq A_i$ for all $i$ also implies that the union of the $B_i$ is contained in the union of the $A_i$: $bigcup_{i=1}^infty B_i subseteq bigcup_{i=1}^infty A_i$. This is half of the second bullet point above. The other half requires showing that $bigcup_{i=1}^infty A_i subseteq bigcup_{i=1}^infty B_i$. If $x in bigcup_{i=1}^infty A_i$, then $x in A_i$ for some $i$, or possibly more than one $i$. For instance, maybe $x$ is in $A_3$, $A_4$, and $A_6$ (and none of the others). How do we know which $B_i$ it is in? By definition, $B_4$ does not contain any of the elements in $A_3$, as they are cut away. Similarly, $B_6$ does not contain any of the elements in $A_3$. So $x$ cannot be in $B_4$ or $B_6$. $B_3$ contains all the elements of $A_3$ that aren't also in $A_1$ or $A_2$. Since $x$ is not in $A_1$ or $A_2$, it doesn't get "cut away" from $A_3$ when we define $B_3$. Hence $x in B_3$. In general, if we know $x in A_{i_1},A_{i_2},dots$ where $i_1<i_2<cdots$, then we know $x in B_{i_1}$.
Finally, we need to show that $B_1,B_2,dots$ are disjoint, i.e., for any $i neq j$, $B_i cap B_j = emptyset$. Suppose $i neq j$, and without loss of generality we can assume $i<j$ (otherwise just re-name the indices so that this is true). Then $B_j$ is defined by taking $A_j$ and removing all of the elements of $A_1,A_2,dots,A_{j-1}$. In particular, since $i<j$, all of the elements of $A_i$ are removed from $B_j$. And since $B_i subseteq A_i$, we know all of the elements of $B_i$ are removed from $B_j$. So they have to be disjoint. If you want to prove this symbolically, we have
begin{align*}
B_i cap B_j &subseteq A_i cap left(A_j - bigcup_{k=1}^{j-1}A_kright)\
&=A_i cap left(A_j cap left(bigcup_{k=1}^{j-1} A_kright)^c right)\
&= A_i capleft(A_j cap left(bigcap_{k=1}^{j-1}A_k^cright)right)\
&subseteq A_i cap A_i^c=emptyset.
end{align*}
So $B_i cap B_j subseteq emptyset$, which implies $B_i cap B_j = emptyset$.
Now we have verified all three bullet points, so the inequality follows.
answered Jan 29 at 15:45
kccukccu
10.8k11229
answered Jan 29 at 15:45
kccukccu
10.8k11229
answered Jan 29 at 15:45
kccukccu
10.8k11229
answered Jan 29 at 15:45
kccukccu
10.8k11229
10.8k11229
$begingroup$
Thank you very much, this was extremely helpful.
$endgroup$
– M. Clay
Jan 29 at 16:20
$begingroup$
If your question has been answered, you can click the checkmark next to my answer to accept it.
$endgroup$
– kccu
Jan 29 at 18:52
add a comment |
$begingroup$
Thank you very much, this was extremely helpful.
$endgroup$
– M. Clay
Jan 29 at 16:20
$begingroup$
If your question has been answered, you can click the checkmark next to my answer to accept it.
$endgroup$
– kccu
Jan 29 at 18:52
$begingroup$
Thank you very much, this was extremely helpful.
$endgroup$
– M. Clay
Jan 29 at 16:20
$begingroup$
Thank you very much, this was extremely helpful.
$endgroup$
– M. Clay
Jan 29 at 16:20
$begingroup$
If your question has been answered, you can click the checkmark next to my answer to accept it.
$endgroup$
– kccu
Jan 29 at 18:52
$begingroup$
If your question has been answered, you can click the checkmark next to my answer to accept it.
$endgroup$
– kccu
Jan 29 at 18:52
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3092293%2fcould-someone-explain-booles-inequality-proof-to-me%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
$begingroup$
What proof? What part don't you understand? I can copy and paste the proof from Wikipedia (en.wikipedia.org/wiki/Boole%27s_inequality) into an answer, but that won't really help you unless you tell us which part you don't get.
$endgroup$
– kccu
Jan 29 at 15:17
$begingroup$
The proof without induction.
$endgroup$
– M. Clay
Jan 29 at 15:18
1
$begingroup$
Again, what part of it are you having trouble with?
$endgroup$
– kccu
Jan 29 at 15:21
$begingroup$
When the sets get modified.
$endgroup$
– M. Clay
Jan 29 at 15:22