Computing the probability of intersection

Abstract

Let ${\Omega }_1,\dots ,{\Omega }_m$ be probability spaces, let $\Omega ={\Omega }_1\times \cdots \times {\Omega }_m$ be their product and let $A_1,\dots ,A_n\subset \Omega$ be events. Suppose that each event $A_i$ depends on $r_i$ coordinates of a point $x\in \Omega$, $x=\left({\xi }_1,\dots ,{\xi }_m\right)$, and that for each event $A_i$ there are ${\Delta }_i$ of other events $A_j$ that depend on some of the coordinates that $A_i$ depends on. Let $\Delta =\max \{5,{\Delta }_i:i=1,\dots ,n\}$ and let ${\mu }_i=\min \{r_i,{\Delta }_i+1\}$ for $i=1,\dots ,n$. We prove that if $P(A_i)<(3\Delta {)}^{-3{\mu }_i}$ for all $i$, then for any $0<\epsilon <1$, the probability $P\left({\bigcap }_{i=1}^n{\overline{A}}_i\right)$ of the intersection of the complements of all $A_i$ can be computed within relative error $\epsilon$ in polynomial time from the probabilities $P\left(A_{i_1}\cap \dots \cap A_{i_k}\right)$ of $k$-wise intersections of the events $A_i$ for $k=e^{O(\Delta )}\ln (n/\epsilon )$.

22 pages, various improvements

References in corpus (5)

• The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
• Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
• The Ising Partition Function: Zeros and Deterministic Approximation
• Weighted counting of solutions to sparse systems of equations
• Fundamentals of Partial Rejection Sampling