Computing the probability of intersection

Abstract

Let $\hat{I}{\text{c◯}}_1,\dots ,\hat{I}{\text{c◯}}_m$ be probability spaces, let $\hat{I}\text{c◯}=\hat{I}{\text{c◯}}_1\times \cdots \times \hat{I}{\text{c◯}}_m$ be their product and let $A_1,\dots ,A_n\subset \hat{I}\text{c◯}$ be events. Suppose that each event $A_i$ depends on $r_i$ coordinates of a point $x\in \hat{I}\text{c◯}$, $x=\left(\hat{I}{¾}_1,\dots ,\hat{I}{¾}_m\right)$, and that for each event $A_i$ there are $\hat{I}{”}_i$ of other events $A_j$ that depend on some of the coordinates that $A_i$ depends on. Let $\hat{I}”=\max \{5,\hat{I}{”}_i:i=1,\dots ,n\}$ and let $\hat{I}{¼}_i=\min \{r_i,\hat{I}{”}_i+1\}$ for $i=1,\dots ,n$. We prove that if $P(A_i)<(3\hat{I}”{)}^{-3\hat{I}{¼}_i}$ for all $i$, then for any $0<\hat{I}\mu <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 $\hat{I}\mu$ 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(\hat{I}”)}\ln (n/\hat{I}\mu )$.

22 pages, various improvements