Czy znane są skuteczne granice ogólne w stylu Bonferroniego?

Klasycznym problemem w teorii prawdopodobieństwa jest wyrażenie prawdopodobieństwa zdarzenia w kategoriach bardziej specyficznych zdarzeń. W najprostszym przypadku można powiedzieć . Write LET'S za zdarzenie . $P[A \cup B] = P[A] + P[B] - P[A \cap B]$ $AB$ $A \cap B$

Istnieją zatem pewne sposoby na powiązanie , bez zakładania niezależności skończonej liczby zdarzeń . Bonferroniego dało górna granica (jest czasem przypisać Boole'a ) i Kounias rafinowany to $P[\cup A_i]$ $A_i$

P [\cup A_{i}] \leq \sum P [A_{i}]

$P[\cup A_i] \le \sum P[A_i]$

P [\cup A_{i}] \leq \sum_{i} P [A_{i}] - max_{j} \sum_{i \neq j} P [A_{i} A_{j}] .

$P[\cup A_i] \le \sum_i P[A_i] - \max_j \sum_{i \ne j} P[A_i A_j].$

Strukturę zależności zdarzeń można traktować jako ważony hipergraf z wierzchołkami $A_i$ , przy czym ciężar krawędzi reprezentuje prawdopodobieństwo zdarzenia związanego z przecięciem wierzchołków na krawędzi.

Argument stylu włączenia / wykluczenia uwzględnia coraz większe podzbiory zdarzeń razem. Te otrzymując granic Bonferroniego . Te granice używają wszystkich wag dla krawędzi do pewnego rozmiaru $k$ .

Jeśli struktura zależności jest „wystarczająco ładna”, to można użyć lokalnej lematy Lovásza, aby ograniczyć prawdopodobieństwo od skrajnych wartości 0 i 1. W przeciwieństwie do podejścia Bonferroniego, LLL wykorzystuje dość zgrubne informacje o strukturze zależności.

Załóżmy teraz, że stosunkowo niewiele wag w strukturze zależności jest niezerowe. Ponadto, załóżmy, że istnieje wiele zdarzeń, które są niezależne parami, ale nie są niezależne (i bardziej ogólnie, całkiem możliwe jest, że zestaw $k$ zdarzeń nie jest wzajemnie niezależny, ale jest $r$ -niezależny dla każdego $r < k$ ).

Czy możliwe jest jawne wykorzystanie struktury zależności zdarzeń w celu ulepszenia granic Bonferroni / Kounias w sposób, który można skutecznie obliczyć?

Spodziewam się, że odpowiedź brzmi „tak” i doceniłbym wskaźniki do odniesień. Zdaję sobie sprawę z pracy Huntera z 1976 roku, ale dotyczy ona tylko zależności parowych. Hunter rozważa rozciąganie drzew na wykresie utworzonym przez ignorowanie krawędzi w strukturze zależności wielkości 3 lub większej.

David Hunter, „Górna granica prawdopodobieństwa związku” , Journal of Applied Probability 13 597–603. http://www.jstor.org/stable/3212481

reference-request pr.probability

— András Salamon
źródło

Myślę, że odpowiedź znajdziesz w artykule „Approximate Inclusion-Exclusion” autorstwa Linial i Nisana: http://www.cs.huji.ac.il/~nati/PAPERS/approx_incl_excl.pdf

— Aryeh
źródło

Wygląda to na bardzo istotne (oficjalny link to link.springer.com/article/10.1007/BF02128670 ); istnieje również link link. springer.com/article/10.1007/BF01271266 autorstwa Jeffa Kahna, Nathana Liniala i Alexa Samorodnitsky'ego.

— András Salamon,