Mixing
How do we prove the union bound inequality (Boole's inequality) for infinite sets?
$begingroup$
I am aware that Boole's inequality can be proved by induction. How do we extend these results to an infinite set? (since induction cannot be applied in this case)
P($bigcuplimits_{i=1}^{infty} A_i$) $leq$ $sum limits_{i=1}^{infty} P(A_i)$
probability
asked Jan 14 '18 at 12:53
Akankshita DashAkankshita Dash
11227
$endgroup$
add a comment |
$begingroup$
I am aware that Boole's inequality can be proved by induction. How do we extend these results to an infinite set? (since induction cannot be applied in this case)
P($bigcuplimits_{i=1}^{infty} A_i$) $leq$ $sum limits_{i=1}^{infty} P(A_i)$
probability
asked Jan 14 '18 at 12:53
Akankshita DashAkankshita Dash
11227
$endgroup$
add a comment |
$begingroup$
I am aware that Boole's inequality can be proved by induction. How do we extend these results to an infinite set? (since induction cannot be applied in this case)
P($bigcuplimits_{i=1}^{infty} A_i$) $leq$ $sum limits_{i=1}^{infty} P(A_i)$
probability
asked Jan 14 '18 at 12:53
Akankshita DashAkankshita Dash
11227
$endgroup$
I am aware that Boole's inequality can be proved by induction. How do we extend these results to an infinite set? (since induction cannot be applied in this case)
P($bigcuplimits_{i=1}^{infty} A_i$) $leq$ $sum limits_{i=1}^{infty} P(A_i)$
probability
probability
asked Jan 14 '18 at 12:53
Akankshita DashAkankshita Dash
11227
asked Jan 14 '18 at 12:53
Akankshita DashAkankshita Dash
11227
asked Jan 14 '18 at 12:53
Akankshita DashAkankshita Dash
11227
asked Jan 14 '18 at 12:53
Akankshita DashAkankshita Dash
11227
asked Jan 14 '18 at 12:53
Akankshita DashAkankshita Dash
11227
11227
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Define $B_i = A_i backslash bigcup^{i-1}_{j=1} A_j$, then we see that $bigcup^{i}_{j=1} B_j=bigcup^{i}_{j=1} A_j$, so $bigcup^{infty}_{j=1} B_j=bigcup^{infty}_{j=1} A_j$. Also note that $B_jsubseteq A_j$, so $ mathbb P (B_j) leq mathbb P(A_j)$ and thus
$$mathbb P (bigcup^{infty}_{j=1}A_j) = mathbb P (bigcup^{infty}_{j=1}B_j) = sum^{infty}_{j=1} mathbb P (B_j) leq sum^{infty}_{j=1} mathbb P(A_j)$$
where the second equality holds due to all $B_j$ being pairwise disjoint.
answered Jan 14 '18 at 13:01
The PhenotypeThe Phenotype
4,77491733
$endgroup$
add a comment |
$begingroup$
Alternatively, let $f(X)$ be the indicator that $Xinbigcup_i A_i$ and let $g(X)$ denote the number of sets $A_i$ that contain $X$; it might for some $X$ values be infinite. Clearly $f(X)le g(X)$ with probability $1$. Take expectations, so $E(f(X))le E(g(X))$.
answered Jan 14 '18 at 13:37
kimchi loverkimchi lover
11k31128
$endgroup$
add a comment |
Your Answer
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%2f2604788%2fhow-do-we-prove-the-union-bound-inequality-booles-inequality-for-infinite-set%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Define $B_i = A_i backslash bigcup^{i-1}_{j=1} A_j$, then we see that $bigcup^{i}_{j=1} B_j=bigcup^{i}_{j=1} A_j$, so $bigcup^{infty}_{j=1} B_j=bigcup^{infty}_{j=1} A_j$. Also note that $B_jsubseteq A_j$, so $ mathbb P (B_j) leq mathbb P(A_j)$ and thus
$$mathbb P (bigcup^{infty}_{j=1}A_j) = mathbb P (bigcup^{infty}_{j=1}B_j) = sum^{infty}_{j=1} mathbb P (B_j) leq sum^{infty}_{j=1} mathbb P(A_j)$$
where the second equality holds due to all $B_j$ being pairwise disjoint.
answered Jan 14 '18 at 13:01
The PhenotypeThe Phenotype
4,77491733
$endgroup$
add a comment |
$begingroup$
Define $B_i = A_i backslash bigcup^{i-1}_{j=1} A_j$, then we see that $bigcup^{i}_{j=1} B_j=bigcup^{i}_{j=1} A_j$, so $bigcup^{infty}_{j=1} B_j=bigcup^{infty}_{j=1} A_j$. Also note that $B_jsubseteq A_j$, so $ mathbb P (B_j) leq mathbb P(A_j)$ and thus
$$mathbb P (bigcup^{infty}_{j=1}A_j) = mathbb P (bigcup^{infty}_{j=1}B_j) = sum^{infty}_{j=1} mathbb P (B_j) leq sum^{infty}_{j=1} mathbb P(A_j)$$
where the second equality holds due to all $B_j$ being pairwise disjoint.
answered Jan 14 '18 at 13:01
The PhenotypeThe Phenotype
4,77491733
$endgroup$
add a comment |
$begingroup$
Define $B_i = A_i backslash bigcup^{i-1}_{j=1} A_j$, then we see that $bigcup^{i}_{j=1} B_j=bigcup^{i}_{j=1} A_j$, so $bigcup^{infty}_{j=1} B_j=bigcup^{infty}_{j=1} A_j$. Also note that $B_jsubseteq A_j$, so $ mathbb P (B_j) leq mathbb P(A_j)$ and thus
$$mathbb P (bigcup^{infty}_{j=1}A_j) = mathbb P (bigcup^{infty}_{j=1}B_j) = sum^{infty}_{j=1} mathbb P (B_j) leq sum^{infty}_{j=1} mathbb P(A_j)$$
where the second equality holds due to all $B_j$ being pairwise disjoint.
answered Jan 14 '18 at 13:01
The PhenotypeThe Phenotype
4,77491733
$endgroup$
Define $B_i = A_i backslash bigcup^{i-1}_{j=1} A_j$, then we see that $bigcup^{i}_{j=1} B_j=bigcup^{i}_{j=1} A_j$, so $bigcup^{infty}_{j=1} B_j=bigcup^{infty}_{j=1} A_j$. Also note that $B_jsubseteq A_j$, so $ mathbb P (B_j) leq mathbb P(A_j)$ and thus
$$mathbb P (bigcup^{infty}_{j=1}A_j) = mathbb P (bigcup^{infty}_{j=1}B_j) = sum^{infty}_{j=1} mathbb P (B_j) leq sum^{infty}_{j=1} mathbb P(A_j)$$
where the second equality holds due to all $B_j$ being pairwise disjoint.
answered Jan 14 '18 at 13:01
The PhenotypeThe Phenotype
4,77491733
answered Jan 14 '18 at 13:01
The PhenotypeThe Phenotype
4,77491733
answered Jan 14 '18 at 13:01
The PhenotypeThe Phenotype
4,77491733
answered Jan 14 '18 at 13:01
The PhenotypeThe Phenotype
4,77491733
4,77491733
add a comment |
add a comment |
$begingroup$
Alternatively, let $f(X)$ be the indicator that $Xinbigcup_i A_i$ and let $g(X)$ denote the number of sets $A_i$ that contain $X$; it might for some $X$ values be infinite. Clearly $f(X)le g(X)$ with probability $1$. Take expectations, so $E(f(X))le E(g(X))$.
answered Jan 14 '18 at 13:37
kimchi loverkimchi lover
11k31128
$endgroup$
add a comment |
$begingroup$
Alternatively, let $f(X)$ be the indicator that $Xinbigcup_i A_i$ and let $g(X)$ denote the number of sets $A_i$ that contain $X$; it might for some $X$ values be infinite. Clearly $f(X)le g(X)$ with probability $1$. Take expectations, so $E(f(X))le E(g(X))$.
answered Jan 14 '18 at 13:37
kimchi loverkimchi lover
11k31128
$endgroup$
add a comment |
$begingroup$
Alternatively, let $f(X)$ be the indicator that $Xinbigcup_i A_i$ and let $g(X)$ denote the number of sets $A_i$ that contain $X$; it might for some $X$ values be infinite. Clearly $f(X)le g(X)$ with probability $1$. Take expectations, so $E(f(X))le E(g(X))$.
answered Jan 14 '18 at 13:37
kimchi loverkimchi lover
11k31128
$endgroup$
Alternatively, let $f(X)$ be the indicator that $Xinbigcup_i A_i$ and let $g(X)$ denote the number of sets $A_i$ that contain $X$; it might for some $X$ values be infinite. Clearly $f(X)le g(X)$ with probability $1$. Take expectations, so $E(f(X))le E(g(X))$.
answered Jan 14 '18 at 13:37
kimchi loverkimchi lover
11k31128
answered Jan 14 '18 at 13:37
kimchi loverkimchi lover
11k31128
answered Jan 14 '18 at 13:37
kimchi loverkimchi lover
11k31128
answered Jan 14 '18 at 13:37
kimchi loverkimchi lover
11k31128
11k31128
add a comment |
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%2f2604788%2fhow-do-we-prove-the-union-bound-inequality-booles-inequality-for-infinite-set%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
