Theorems like the Lovász Local Lemma?
$begingroup$
The Lovász Local Lemma gives a probability bound in a context where there are many events that are "not quite" independent.
What other theorems exist in this genre? That is, what other theorems have a hypothesis of the form "Let events E_1, E_2, ... satisfy [relaxed form of independence]" and a conclusion of the form "Then the probability of [compound event] satisfies [inequality]"?
(I hope this question isn't too broad. I frequently encounter problems with events that are "almost independent", either in the sense that most subsets are independent or in the sense that the probabilities of compound events are well-approximated by assuming independence, and I am looking for general tools that may be helpful when these situations come up.)
pr.probability probabilistic-method
asked yesterday
AustinAustin
21114
$endgroup$
add a comment |
$begingroup$
The Lovász Local Lemma gives a probability bound in a context where there are many events that are "not quite" independent.
What other theorems exist in this genre? That is, what other theorems have a hypothesis of the form "Let events E_1, E_2, ... satisfy [relaxed form of independence]" and a conclusion of the form "Then the probability of [compound event] satisfies [inequality]"?
(I hope this question isn't too broad. I frequently encounter problems with events that are "almost independent", either in the sense that most subsets are independent or in the sense that the probabilities of compound events are well-approximated by assuming independence, and I am looking for general tools that may be helpful when these situations come up.)
pr.probability probabilistic-method
asked yesterday
AustinAustin
21114
$endgroup$
1
$begingroup$
See pdfs.semanticscholar.org/6631/…
$endgroup$
– Sam Hopkins
yesterday
2
$begingroup$
Talagrand’s concentration inequality in particular is very powerful for this kind of thing.
$endgroup$
– Sam Hopkins
yesterday
add a comment |
$begingroup$
The Lovász Local Lemma gives a probability bound in a context where there are many events that are "not quite" independent.
What other theorems exist in this genre? That is, what other theorems have a hypothesis of the form "Let events E_1, E_2, ... satisfy [relaxed form of independence]" and a conclusion of the form "Then the probability of [compound event] satisfies [inequality]"?
(I hope this question isn't too broad. I frequently encounter problems with events that are "almost independent", either in the sense that most subsets are independent or in the sense that the probabilities of compound events are well-approximated by assuming independence, and I am looking for general tools that may be helpful when these situations come up.)
pr.probability probabilistic-method
asked yesterday
AustinAustin
21114
$endgroup$
The Lovász Local Lemma gives a probability bound in a context where there are many events that are "not quite" independent.
What other theorems exist in this genre? That is, what other theorems have a hypothesis of the form "Let events E_1, E_2, ... satisfy [relaxed form of independence]" and a conclusion of the form "Then the probability of [compound event] satisfies [inequality]"?
(I hope this question isn't too broad. I frequently encounter problems with events that are "almost independent", either in the sense that most subsets are independent or in the sense that the probabilities of compound events are well-approximated by assuming independence, and I am looking for general tools that may be helpful when these situations come up.)
pr.probability probabilistic-method
pr.probability probabilistic-method
asked yesterday
AustinAustin
21114
asked yesterday
AustinAustin
21114
asked yesterday
AustinAustin
21114
asked yesterday
AustinAustin
21114
asked yesterday
AustinAustin
21114
21114
1
$begingroup$
See pdfs.semanticscholar.org/6631/…
$endgroup$
– Sam Hopkins
yesterday
2
$begingroup$
Talagrand’s concentration inequality in particular is very powerful for this kind of thing.
$endgroup$
– Sam Hopkins
yesterday
add a comment |
1
$begingroup$
See pdfs.semanticscholar.org/6631/…
$endgroup$
– Sam Hopkins
yesterday
2
$begingroup$
Talagrand’s concentration inequality in particular is very powerful for this kind of thing.
$endgroup$
– Sam Hopkins
yesterday
1
1
$begingroup$
See pdfs.semanticscholar.org/6631/…
$endgroup$
– Sam Hopkins
yesterday
$begingroup$
See pdfs.semanticscholar.org/6631/…
$endgroup$
– Sam Hopkins
yesterday
2
2
$begingroup$
Talagrand’s concentration inequality in particular is very powerful for this kind of thing.
$endgroup$
– Sam Hopkins
yesterday
$begingroup$
Talagrand’s concentration inequality in particular is very powerful for this kind of thing.
$endgroup$
– Sam Hopkins
yesterday
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
A large number of results for sums $W$ of possibly dependent indicators of events (that is, for sums of possibly dependent Bernoulli random variables) $X_i$ have been obtained by the Chen--Stein method. See e.g. Theorem 1, which gives an upper bound on the total variation distance between the distribution of such a sum $W$ and a corresponding Poisson distribution in terms of certain characteristics $b_1,b_2,b_3$ of the strength of the dependence between the $X_i$'s (defined in formulas (4)--(6) of that paper).
answered yesterday
Iosif PinelisIosif Pinelis
19.9k22259
$endgroup$
add a comment |
$begingroup$
Does exchangeability qualify as a "relaxed form of independence"? There are a number of results for exchangeable sequences, for example Hong & Lee for a Weak Law of Large Numbers or Fortini, Ladelli & Regazzini for a Central Limit Theorem;
answered yesterday
Robin RyderRobin Ryder
1114
New contributor
Robin Ryder is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$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: "504"
};
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%2fmathoverflow.net%2fquestions%2f325465%2ftheorems-like-the-lov%25c3%25a1sz-local-lemma%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$
A large number of results for sums $W$ of possibly dependent indicators of events (that is, for sums of possibly dependent Bernoulli random variables) $X_i$ have been obtained by the Chen--Stein method. See e.g. Theorem 1, which gives an upper bound on the total variation distance between the distribution of such a sum $W$ and a corresponding Poisson distribution in terms of certain characteristics $b_1,b_2,b_3$ of the strength of the dependence between the $X_i$'s (defined in formulas (4)--(6) of that paper).
answered yesterday
Iosif PinelisIosif Pinelis
19.9k22259
$endgroup$
add a comment |
$begingroup$
A large number of results for sums $W$ of possibly dependent indicators of events (that is, for sums of possibly dependent Bernoulli random variables) $X_i$ have been obtained by the Chen--Stein method. See e.g. Theorem 1, which gives an upper bound on the total variation distance between the distribution of such a sum $W$ and a corresponding Poisson distribution in terms of certain characteristics $b_1,b_2,b_3$ of the strength of the dependence between the $X_i$'s (defined in formulas (4)--(6) of that paper).
answered yesterday
Iosif PinelisIosif Pinelis
19.9k22259
$endgroup$
add a comment |
$begingroup$
A large number of results for sums $W$ of possibly dependent indicators of events (that is, for sums of possibly dependent Bernoulli random variables) $X_i$ have been obtained by the Chen--Stein method. See e.g. Theorem 1, which gives an upper bound on the total variation distance between the distribution of such a sum $W$ and a corresponding Poisson distribution in terms of certain characteristics $b_1,b_2,b_3$ of the strength of the dependence between the $X_i$'s (defined in formulas (4)--(6) of that paper).
answered yesterday
Iosif PinelisIosif Pinelis
19.9k22259
$endgroup$
A large number of results for sums $W$ of possibly dependent indicators of events (that is, for sums of possibly dependent Bernoulli random variables) $X_i$ have been obtained by the Chen--Stein method. See e.g. Theorem 1, which gives an upper bound on the total variation distance between the distribution of such a sum $W$ and a corresponding Poisson distribution in terms of certain characteristics $b_1,b_2,b_3$ of the strength of the dependence between the $X_i$'s (defined in formulas (4)--(6) of that paper).
answered yesterday
Iosif PinelisIosif Pinelis
19.9k22259
answered yesterday
Iosif PinelisIosif Pinelis
19.9k22259
answered yesterday
Iosif PinelisIosif Pinelis
19.9k22259
answered yesterday
Iosif PinelisIosif Pinelis
19.9k22259
19.9k22259
add a comment |
add a comment |
$begingroup$
Does exchangeability qualify as a "relaxed form of independence"? There are a number of results for exchangeable sequences, for example Hong & Lee for a Weak Law of Large Numbers or Fortini, Ladelli & Regazzini for a Central Limit Theorem;
answered yesterday
Robin RyderRobin Ryder
1114
New contributor
Robin Ryder is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
Does exchangeability qualify as a "relaxed form of independence"? There are a number of results for exchangeable sequences, for example Hong & Lee for a Weak Law of Large Numbers or Fortini, Ladelli & Regazzini for a Central Limit Theorem;
answered yesterday
Robin RyderRobin Ryder
1114
New contributor
Robin Ryder is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
Does exchangeability qualify as a "relaxed form of independence"? There are a number of results for exchangeable sequences, for example Hong & Lee for a Weak Law of Large Numbers or Fortini, Ladelli & Regazzini for a Central Limit Theorem;
answered yesterday
Robin RyderRobin Ryder
1114
New contributor
Robin Ryder is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
Does exchangeability qualify as a "relaxed form of independence"? There are a number of results for exchangeable sequences, for example Hong & Lee for a Weak Law of Large Numbers or Fortini, Ladelli & Regazzini for a Central Limit Theorem;
answered yesterday
Robin RyderRobin Ryder
1114
New contributor
Robin Ryder is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 21 hours ago
answered yesterday
Robin RyderRobin Ryder
1114
New contributor
Robin Ryder is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered yesterday
Robin RyderRobin Ryder
1114
answered yesterday
Robin RyderRobin Ryder
1114
1114
New contributor
Robin Ryder is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Robin Ryder is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Robin Ryder is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
add a comment |
Thanks for contributing an answer to MathOverflow!
- 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%2fmathoverflow.net%2fquestions%2f325465%2ftheorems-like-the-lov%25c3%25a1sz-local-lemma%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$
See pdfs.semanticscholar.org/6631/…
$endgroup$
– Sam Hopkins
yesterday
2
$begingroup$
Talagrand’s concentration inequality in particular is very powerful for this kind of thing.
$endgroup$
– Sam Hopkins
yesterday