Computing the probability of intersection
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918140313600000 |
|---|---|
| author | Barvinok, Alexander |
| author_facet | Barvinok, Alexander |
| contents | Let $Ω_1, \ldots, Ω_m$ be probability spaces, let $Ω=Ω_1 \times \cdots \times Ω_m$ be their product and let $A_1, \ldots, A_n \subset Ω$ be events. Suppose that each event $A_i$ depends on $r_i$ coordinates of a point $x \in Ω$, $x=\left(ξ_1, \ldots, ξ_m\right)$, and that for each event $A_i$ there are $Δ_i$ of other events $A_j$ that depend on some of the coordinates that $A_i$ depends on. Let $Δ=\max\{5,\ Δ_i: i=1, \ldots, n\}$ and let $μ_i=\min\{r_i,\ Δ_i+1\}$ for $i=1, \ldots, n$. We prove that if $P(A_i) < (3Δ)^{-3μ_i}$ for all $i$, then for any $0 < ε< 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 $ε$ in polynomial time from the probabilities $P\left(A_{i_1} \cap \ldots \cap A_{i_k}\right)$ of $k$-wise intersections of the events $A_i$ for $k = e^{O(Δ)} \ln (n/ε)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_10329 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Computing the probability of intersection Barvinok, Alexander Probability Data Structures and Algorithms Combinatorics 60C05, 68Q87, 68W05, 30C15 Let $Ω_1, \ldots, Ω_m$ be probability spaces, let $Ω=Ω_1 \times \cdots \times Ω_m$ be their product and let $A_1, \ldots, A_n \subset Ω$ be events. Suppose that each event $A_i$ depends on $r_i$ coordinates of a point $x \in Ω$, $x=\left(ξ_1, \ldots, ξ_m\right)$, and that for each event $A_i$ there are $Δ_i$ of other events $A_j$ that depend on some of the coordinates that $A_i$ depends on. Let $Δ=\max\{5,\ Δ_i: i=1, \ldots, n\}$ and let $μ_i=\min\{r_i,\ Δ_i+1\}$ for $i=1, \ldots, n$. We prove that if $P(A_i) < (3Δ)^{-3μ_i}$ for all $i$, then for any $0 < ε< 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 $ε$ in polynomial time from the probabilities $P\left(A_{i_1} \cap \ldots \cap A_{i_k}\right)$ of $k$-wise intersections of the events $A_i$ for $k = e^{O(Δ)} \ln (n/ε)$. |
| title | Computing the probability of intersection |
| topic | Probability Data Structures and Algorithms Combinatorics 60C05, 68Q87, 68W05, 30C15 |
| url | https://arxiv.org/abs/2507.10329 |