Theorems like the Lovász Local Lemma?












8












$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







share|cite|improve this question









$endgroup$








  • 1




    $begingroup$
    See pdfs.semanticscholar.org/6631/…
    $endgroup$
    – Sam Hopkins
    7 hours ago






  • 2




    $begingroup$
    Talagrand’s concentration inequality in particular is very powerful for this kind of thing.
    $endgroup$
    – Sam Hopkins
    7 hours ago
















8












$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







share|cite|improve this question









$endgroup$








  • 1




    $begingroup$
    See pdfs.semanticscholar.org/6631/…
    $endgroup$
    – Sam Hopkins
    7 hours ago






  • 2




    $begingroup$
    Talagrand’s concentration inequality in particular is very powerful for this kind of thing.
    $endgroup$
    – Sam Hopkins
    7 hours ago














8












8








8


1



$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







share|cite|improve this question









$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






share|cite|improve this question













share|cite|improve this question











share|cite|improve this question




share|cite|improve this question










asked 8 hours ago









AustinAustin

20113




20113








  • 1




    $begingroup$
    See pdfs.semanticscholar.org/6631/…
    $endgroup$
    – Sam Hopkins
    7 hours ago






  • 2




    $begingroup$
    Talagrand’s concentration inequality in particular is very powerful for this kind of thing.
    $endgroup$
    – Sam Hopkins
    7 hours ago














  • 1




    $begingroup$
    See pdfs.semanticscholar.org/6631/…
    $endgroup$
    – Sam Hopkins
    7 hours ago






  • 2




    $begingroup$
    Talagrand’s concentration inequality in particular is very powerful for this kind of thing.
    $endgroup$
    – Sam Hopkins
    7 hours ago








1




1




$begingroup$
See pdfs.semanticscholar.org/6631/…
$endgroup$
– Sam Hopkins
7 hours ago




$begingroup$
See pdfs.semanticscholar.org/6631/…
$endgroup$
– Sam Hopkins
7 hours ago




2




2




$begingroup$
Talagrand’s concentration inequality in particular is very powerful for this kind of thing.
$endgroup$
– Sam Hopkins
7 hours ago




$begingroup$
Talagrand’s concentration inequality in particular is very powerful for this kind of thing.
$endgroup$
– Sam Hopkins
7 hours ago










2 Answers
2






active

oldest

votes


















7












$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).






share|cite|improve this answer









$endgroup$





















    0












    $begingroup$

    Does exchangeability qualify as "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;






    share|cite|improve this answer








    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$













      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
      });


      }
      });














      draft saved

      draft discarded


















      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









      7












      $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).






      share|cite|improve this answer









      $endgroup$


















        7












        $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).






        share|cite|improve this answer









        $endgroup$
















          7












          7








          7





          $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).






          share|cite|improve this answer









          $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).







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          answered 7 hours ago









          Iosif PinelisIosif Pinelis

          19.9k22259




          19.9k22259























              0












              $begingroup$

              Does exchangeability qualify as "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;






              share|cite|improve this answer








              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$


















                0












                $begingroup$

                Does exchangeability qualify as "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;






                share|cite|improve this answer








                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$
















                  0












                  0








                  0





                  $begingroup$

                  Does exchangeability qualify as "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;






                  share|cite|improve this answer








                  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 "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;







                  share|cite|improve this answer








                  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.









                  share|cite|improve this answer



                  share|cite|improve this answer






                  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 3 hours ago









                  Robin RyderRobin Ryder

                  1012




                  1012




                  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.






























                      draft saved

                      draft discarded




















































                      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.




                      draft saved


                      draft discarded














                      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





















































                      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







                      -

                      Popular posts from this blog

                      How to make a Squid Proxy server?

                      Image
                      1 I want to set up squid proxy server for monitoring user activity in a network and Internet Web URL filtering for user. I also want to configure the user login, user log, user access group, and block unwanted web sites in my network. Please help me and guide me the full process to do this. server proxy squid share | improve this question edited Jul 31 '12 at 14:45 Jorge Castro 37.1k 107 422 617 asked Jul 31 '12 at 5:16 Goivind Tiwari Goivind Tiwari
                      Read more

                      Is this a new Fibonacci Identity?

                      Image
                      6 1 $begingroup$ I have found the following Fibonacci Identity (and proved it). If $F_n$ denotes the nth Fibonacci Number, we have the following identity begin{equation} F_{n-r+h}F_{n+k+g+1} - F_{n-r+g}F_{n+k+h+1} = (-1)^{n+r+h+1} F_{g-h}F_{k+r+1} end{equation} where $F_1 = F_2 = 1$ , $r leq n$ , $h leq g$ , and $n, g, k in mathbb{N}$ . It is not too hard to show that this identity subsumes Cassini's Identity, Catalan's Identity, Vajda's Idenity, and d'Ocagne's identity to name a few. I have done a pretty thorough literature review, and I have not found anything like this, but I am still wondering if anyone has seen this identity before? I found this by accident after noticing some patterns in some analysis work I was doing, so if this is already known I would be curious to see w
                      Read more

                      Touch on Surface Book

                      Image
                      0 How can I make touch work on my Surface Book? About my Surface Book: Model: Intel Core i7-6600 U @ 2.60 GHz with 8 GB Ram and Nvidia GPU OS: Ubuntu 17.04 Latest, kernel 4.10.0-13-generic System outputs on Ubuntu: ~$ xinput list ⎡ Virtual core pointer id=2 [master pointer (3)] ⎜ ↳ Virtual core XTEST pointer id=4 [slave pointer (2)] ⎜ ↳ USB OPTICAL MOUSE id=8 [slave pointer (2)] ⎜ ↳ Microsoft Surface Keyboard Consumer Control id=10 [slave pointer (2)] ⎜ ↳ Microsoft Surface Keyboard Touchpad id=11 [slave pointer (2)] ⎣ Virtual core keyboard id=3 [master keyboard (2)] ↳ Virtual core XTEST keyboard id=5 [slave keyboard (3)]
                      Read more