A classic problem in probability theory is to express the probability of an event in terms of more specific events. In the simplest case, one can say $P[A \cup B] = P[A] + P[B] - P[A \cap B]$. Let's write $AB$ for the event $A \cap B$.

There are then some ways to bound $P[\cup A_i]$, without assuming independence of the finitely many events $A_i$. Bonferroni gave the upper bound $$P[\cup A_i] \le \sum P[A_i]$$ (this is sometimes also attributed to Boole), and Kounias refined this to $$P[\cup A_i] \le \sum_i P[A_i] - \max_j \sum_{i \ne j} P[A_i A_j].$$

The dependence structure of the events can be thought of as a weighted hypergraph with vertices $A_i$, with the weight of an edge representing the probability of the event associated with the intersection of the vertices in the edge.

An inclusion-exclusion style argument considers larger and larger subsets of events together. These yield the Bonferroni bounds. These bounds use all weights for edges up to some size $k$.

If the dependence structure is "nice enough", then the Lovász Local Lemma can be used to bound the probability away from the extreme values 0 and 1. In contrast to the Bonferroni approach, the LLL uses quite coarse information about the dependence structure.

Now suppose relatively few weights in the dependence structure are non-zero. Further, suppose that there are many events that are pairwise independent yet are not independent (and more generally, it is quite possible that a set of $k$ events is not mutually independent but is $r$-wise independent for every $r < k$).

Is it possible to explicitly use the dependence structure of events to improve the Bonferroni/Kounias bounds, in a way that can be computed efficiently?

I expect the answer is yes, and would appreciate pointers to references. I am aware of Hunter's paper from 1976, but it only deals with pairwise dependencies. Hunter considers spanning trees in the graph formed by ignoring the edges in the dependence structure of size 3 or greater.


1 Answer 1


I think you'll find the answer in the paper "Approximate Inclusion-Exclusion" by Linial and Nisan: http://www.cs.huji.ac.il/~nati/PAPERS/approx_incl_excl.pdf


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.