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

CC BY-SA 3.0
2015-01-15T18:48:03.900Z
This does look highly relevant (official link is http://link.springer.com/article/10.1007/BF02128670 ); there is also a follow-up http://link.springer.com/article/10.1007/BF01271266 by Jeff Kahn, Nathan Linial, and Alex Samorodnitsky.
András Salamon
CC BY-SA 3.0
2015-01-15T14:03:01.980Z
2015-01-15T14:03:01.980Z
Aryeh
<p>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$.</p>

<p>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 <a href="http://en.wikipedia.org/wiki/Boole%27s_inequality">Boole</a>), 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].$$</p>

<p>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.</p>

<p>An inclusion-exclusion style argument considers larger and larger subsets of events together.  These yield the <a href="http://en.wikipedia.org/wiki/Boole%27s_inequality">Bonferroni bounds</a>.  These bounds use all weights for edges up to some size $k$.</p>

<p>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.  </p>

<p>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 &lt; k$).</p>

<blockquote>
  <p>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?</p>
</blockquote>

<p>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.</p>

<ul>
<li>David Hunter, <em>An Upper Bound for the Probability of a Union</em>, Journal of Applied Probability <strong>13</strong> 597–603.  <a href="http://www.jstor.org/stable/3212481">http://www.jstor.org/stable/3212481</a></li>
</ul>

<reference-request><pr.probability>
Are there efficient general Bonferroni-style bounds known?
András Salamon
# Are there efficient general Bonferroni-style bounds known?

(Asked by: username_0 on 2010-10-22)

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](http://en.wikipedia.org/wiki/Boole%27s_inequality)), 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](http://en.wikipedia.org/wiki/Boole%27s_inequality). 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.

* David Hunter, *An Upper Bound for the Probability of a Union*, Journal of Applied Probability **13** 597–603. <http://www.jstor.org/stable/3212481>

**Tags:** reference-request, pr.probability

---

## 1 answers

### Answer by username_1 on 2015-01-15. Score: 1 | Accepted answer

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>

> **Comments:**
> **username_0**: This does look highly relevant (official link is http://link.springer.com/article/10.1007/BF02128670 ); there is also a follow-up http://link.springer.com/article/10.1007/BF01271266 by Jeff Kahn, Nathan Linial, and Alex Samorodnitsky.  

---

