Computing the probability of intersection

Source abstract

Abstract Let normal upper Omega 1 comma ellipsis comma normal upper Omega Subscript m Baseline Ω 1 , … , Ω m $\Omega _1, \ldots , \Omega _m$ be probability spaces, let bold upper Omega equals normal upper Omega 1 times midline horizontal ellipsis times normal upper Omega Subscript m Ω = Ω 1 × ⋯ × Ω m ${\mathbf \Omega }=\Omega _1 \times \cdots \times \Omega _m$ be their product and let upper A 1 comma ellipsis comma upper A Subscript n Baseline subset of bold upper Omega A 1 , … , A n ⊂ Ω $A_1, \ldots , A_n \subset {\mathbf \Omega }$ be events. Suppose that each event upper A Subscript i A i $A_i$ depends on r Subscript i r i $r_i$ coordinates of a point x element of bold upper Omega x ∈ Ω $x \in {\mathbf \Omega }$ , x equals left parenthesis xi 1 comma ellipsis comma xi Subscript m Baseline right parenthesis x = ( ξ 1 , … , ξ m ) $x=\left (\xi _1, \ldots , \xi _m\right )$ , and that for each event upper A Subscript i A i $A_i$ there are normal upper Delta Subscript i Δ i $\Delta _i$ other events upper A Subscript j A j $A_j$ that depend on some of the coordinates that upper A Subscript i A i $A_i$ depends on. Let normal upper Delta equals max left brace 5 comma normal upper Delta Subscript i Baseline colon i equals 1 comma ellipsis comma n right brace Δ = max { 5 , Δ i : i = 1 , … , n } $\Delta =\max \{5,\ \Delta _i\,:\, i=1, \ldots , n\}$ and let mu Subscript i Baseline equals min left brace r Subscript i Baseline comma normal upper Delta Subscript i Baseline plus 1 right brace μ i = min { r i , Δ i + 1 } $\mu _i=\min \{r_i,\ \Delta _i+1\}$ for i equals 1 comma ellipsis comma n i = 1 , … , n $i=1, \ldots , n$ . We prove that if double struck upper P left parenthesis upper A Subscript i Baseline right parenthesis less than left parenthesis 3 normal upper Delta right parenthesis Superscript minus 3 mu Super Subscript i P ( A i ) < ( 3 Δ ) − 3 μ i ${\mathbb P}(A_i) \lt (3\Delta )^{-3\mu _i}$ for all i i $i$ , then for any 0 less than epsilon less than 1 0 < ϵ < 1 $0 \lt \epsilon \lt 1$ , the probability double struck upper P left parenthesis intersection Underscript i equals 1 Overscript n Endscripts upper A overbar Subscript i Baseline right parenthesis P ( ⋂ i = 1 n A ¯ i ) ${\mathbb P}\left ( \bigcap _{i=1}^n \overline {A}_i\right )$ of the intersection of the complements of all upper A Subscript i A i $A_i$ can be computed within relative error epsilon ϵ $\epsilon$ in polynomial time from the probabilities double struck upper P left parenthesis upper A Subscript i 1 Baseline intersection ellipsis intersection upper A Subscript i Sub Subscript k Subscript Baseline right parenthesis P ( A i 1 ∩ … ∩ A i k ) ${\mathbb P}\left (A_{i_1} \cap \ldots \cap A_{i_k}\right )$ of k k $k$ -wise intersections of the events upper A Subscript i A i $A_i$ for k equals e Superscript upper O left parenthesis normal upper Delta right parenthesis Baseline ln left parenthesis n divided by epsilon right parenthesis k = e O ( Δ ) ln ⁡ ( n / ϵ ) $k = e^{O(\Delta )} \ln (n/\epsilon )$ .