A Question on the Inclusion-Exclusion Principle in Probability Theory
$begingroup$
Let $n geq 3$ be a fixed integer and consider an arbitrary set of the events ${A_i, 1 leq i leq n }$ in the same probability space. Consider the following two sums of probabilities:
begin{align}
S_1 ^{(n)} &= sum_{1 leq i leq n} mathbb{P}(A_i); \
S_2 ^{(n)} &= sum_{1 leq i_1 < i_2 leq n} mathbb{P}(A_{i_1} cap A_{i_2}).
end{align}
The question is whether it holds that $S_1 ^{(n)} geq S_2 ^{(n)}$ and $2 S_1 ^{(n)} geq 3 S_2 ^{(n)}$?
Both inequalities hold for $n = 3$. But I could not have a proof based on induction according to this base case. Anyone has a idea? Thanks very much.
probability probability-theory inclusion-exclusion
edited Dec 25 '18 at 11:49
N. F. Taussig
45.1k103358
asked Dec 25 '18 at 10:29
RichieRichie
394210
$endgroup$
add a comment |
$begingroup$
Let $n geq 3$ be a fixed integer and consider an arbitrary set of the events ${A_i, 1 leq i leq n }$ in the same probability space. Consider the following two sums of probabilities:
begin{align}
S_1 ^{(n)} &= sum_{1 leq i leq n} mathbb{P}(A_i); \
S_2 ^{(n)} &= sum_{1 leq i_1 < i_2 leq n} mathbb{P}(A_{i_1} cap A_{i_2}).
end{align}
The question is whether it holds that $S_1 ^{(n)} geq S_2 ^{(n)}$ and $2 S_1 ^{(n)} geq 3 S_2 ^{(n)}$?
Both inequalities hold for $n = 3$. But I could not have a proof based on induction according to this base case. Anyone has a idea? Thanks very much.
probability probability-theory inclusion-exclusion
edited Dec 25 '18 at 11:49
N. F. Taussig
45.1k103358
asked Dec 25 '18 at 10:29
RichieRichie
394210
$endgroup$
1
$begingroup$
Neither inequality can hold in general as the case when all the events $A_i$ are equal, shows.
$endgroup$
– Did
Dec 25 '18 at 10:38
$begingroup$
@Did Thanks a lot. In case that the events are not identical nor disjoint, which would be of more interest, do the inequalities hold in general?
$endgroup$
– Richie
Dec 25 '18 at 11:13
$begingroup$
The case of identical events serves to show that some specific condition must be added. Of course nonequal events shall also disprove the conjecture: assume for example that $P(A_i)=a$ and $P(A_icap A_j)=b$ for every $i$ and $j$ and consider the limit when $ntoinfty$. Once again, these trivial cases only help to show the inequality cannot hold in general. (Not sure I understand your mention of disjointness since disjoint events automatically fit the conjecture because then $S^{(n)}_2=0$.)
$endgroup$
– Did
Dec 25 '18 at 12:13
add a comment |
$begingroup$
Let $n geq 3$ be a fixed integer and consider an arbitrary set of the events ${A_i, 1 leq i leq n }$ in the same probability space. Consider the following two sums of probabilities:
begin{align}
S_1 ^{(n)} &= sum_{1 leq i leq n} mathbb{P}(A_i); \
S_2 ^{(n)} &= sum_{1 leq i_1 < i_2 leq n} mathbb{P}(A_{i_1} cap A_{i_2}).
end{align}
The question is whether it holds that $S_1 ^{(n)} geq S_2 ^{(n)}$ and $2 S_1 ^{(n)} geq 3 S_2 ^{(n)}$?
Both inequalities hold for $n = 3$. But I could not have a proof based on induction according to this base case. Anyone has a idea? Thanks very much.
probability probability-theory inclusion-exclusion
edited Dec 25 '18 at 11:49
N. F. Taussig
45.1k103358
asked Dec 25 '18 at 10:29
RichieRichie
394210
$endgroup$
Let $n geq 3$ be a fixed integer and consider an arbitrary set of the events ${A_i, 1 leq i leq n }$ in the same probability space. Consider the following two sums of probabilities:
begin{align}
S_1 ^{(n)} &= sum_{1 leq i leq n} mathbb{P}(A_i); \
S_2 ^{(n)} &= sum_{1 leq i_1 < i_2 leq n} mathbb{P}(A_{i_1} cap A_{i_2}).
end{align}
The question is whether it holds that $S_1 ^{(n)} geq S_2 ^{(n)}$ and $2 S_1 ^{(n)} geq 3 S_2 ^{(n)}$?
Both inequalities hold for $n = 3$. But I could not have a proof based on induction according to this base case. Anyone has a idea? Thanks very much.
probability probability-theory inclusion-exclusion
probability probability-theory inclusion-exclusion
edited Dec 25 '18 at 11:49
N. F. Taussig
45.1k103358
asked Dec 25 '18 at 10:29
RichieRichie
394210
edited Dec 25 '18 at 11:49
N. F. Taussig
45.1k103358
asked Dec 25 '18 at 10:29
RichieRichie
394210
edited Dec 25 '18 at 11:49
N. F. Taussig
45.1k103358
edited Dec 25 '18 at 11:49
N. F. Taussig
45.1k103358
edited Dec 25 '18 at 11:49
N. F. Taussig
45.1k103358
45.1k103358
asked Dec 25 '18 at 10:29
RichieRichie
394210
asked Dec 25 '18 at 10:29
RichieRichie
394210
asked Dec 25 '18 at 10:29
RichieRichie
394210
394210
1
$begingroup$
Neither inequality can hold in general as the case when all the events $A_i$ are equal, shows.
$endgroup$
– Did
Dec 25 '18 at 10:38
$begingroup$
@Did Thanks a lot. In case that the events are not identical nor disjoint, which would be of more interest, do the inequalities hold in general?
$endgroup$
– Richie
Dec 25 '18 at 11:13
$begingroup$
The case of identical events serves to show that some specific condition must be added. Of course nonequal events shall also disprove the conjecture: assume for example that $P(A_i)=a$ and $P(A_icap A_j)=b$ for every $i$ and $j$ and consider the limit when $ntoinfty$. Once again, these trivial cases only help to show the inequality cannot hold in general. (Not sure I understand your mention of disjointness since disjoint events automatically fit the conjecture because then $S^{(n)}_2=0$.)
$endgroup$
– Did
Dec 25 '18 at 12:13
add a comment |
1
$begingroup$
Neither inequality can hold in general as the case when all the events $A_i$ are equal, shows.
$endgroup$
– Did
Dec 25 '18 at 10:38
$begingroup$
@Did Thanks a lot. In case that the events are not identical nor disjoint, which would be of more interest, do the inequalities hold in general?
$endgroup$
– Richie
Dec 25 '18 at 11:13
$begingroup$
The case of identical events serves to show that some specific condition must be added. Of course nonequal events shall also disprove the conjecture: assume for example that $P(A_i)=a$ and $P(A_icap A_j)=b$ for every $i$ and $j$ and consider the limit when $ntoinfty$. Once again, these trivial cases only help to show the inequality cannot hold in general. (Not sure I understand your mention of disjointness since disjoint events automatically fit the conjecture because then $S^{(n)}_2=0$.)
$endgroup$
– Did
Dec 25 '18 at 12:13
1
1
$begingroup$
Neither inequality can hold in general as the case when all the events $A_i$ are equal, shows.
$endgroup$
– Did
Dec 25 '18 at 10:38
$begingroup$
Neither inequality can hold in general as the case when all the events $A_i$ are equal, shows.
$endgroup$
– Did
Dec 25 '18 at 10:38
$begingroup$
@Did Thanks a lot. In case that the events are not identical nor disjoint, which would be of more interest, do the inequalities hold in general?
$endgroup$
– Richie
Dec 25 '18 at 11:13
$begingroup$
@Did Thanks a lot. In case that the events are not identical nor disjoint, which would be of more interest, do the inequalities hold in general?
$endgroup$
– Richie
Dec 25 '18 at 11:13
$begingroup$
The case of identical events serves to show that some specific condition must be added. Of course nonequal events shall also disprove the conjecture: assume for example that $P(A_i)=a$ and $P(A_icap A_j)=b$ for every $i$ and $j$ and consider the limit when $ntoinfty$. Once again, these trivial cases only help to show the inequality cannot hold in general. (Not sure I understand your mention of disjointness since disjoint events automatically fit the conjecture because then $S^{(n)}_2=0$.)
$endgroup$
– Did
Dec 25 '18 at 12:13
$begingroup$
The case of identical events serves to show that some specific condition must be added. Of course nonequal events shall also disprove the conjecture: assume for example that $P(A_i)=a$ and $P(A_icap A_j)=b$ for every $i$ and $j$ and consider the limit when $ntoinfty$. Once again, these trivial cases only help to show the inequality cannot hold in general. (Not sure I understand your mention of disjointness since disjoint events automatically fit the conjecture because then $S^{(n)}_2=0$.)
$endgroup$
– Did
Dec 25 '18 at 12:13
add a comment |
0
active
oldest
votes
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%2f3051996%2fa-question-on-the-inclusion-exclusion-principle-in-probability-theory%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f3051996%2fa-question-on-the-inclusion-exclusion-principle-in-probability-theory%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$
Neither inequality can hold in general as the case when all the events $A_i$ are equal, shows.
$endgroup$
– Did
Dec 25 '18 at 10:38
$begingroup$
@Did Thanks a lot. In case that the events are not identical nor disjoint, which would be of more interest, do the inequalities hold in general?
$endgroup$
– Richie
Dec 25 '18 at 11:13
$begingroup$
The case of identical events serves to show that some specific condition must be added. Of course nonequal events shall also disprove the conjecture: assume for example that $P(A_i)=a$ and $P(A_icap A_j)=b$ for every $i$ and $j$ and consider the limit when $ntoinfty$. Once again, these trivial cases only help to show the inequality cannot hold in general. (Not sure I understand your mention of disjointness since disjoint events automatically fit the conjecture because then $S^{(n)}_2=0$.)
$endgroup$
– Did
Dec 25 '18 at 12:13