Computing the probability of intersection

Abstract

Let

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 )$

.