Upper bounds for the probability of a union by multitrees (Q2749132)

An old problem on finding upper bounds for the union probabilities \(P(A_1\cup\cdots\cup A_n)\) in terms of sums of \(P(A_{k_1}\cap\cdots\cap A_{k_i})\) (\(1\leq k_1<\cdots< k_i\leq n\), \(i= 1,\dots, d\)) is studied. The method of proof uses the notion of a hypergraph with \(n\) vertices, called an \(m\)-multitree, where \(m= d-1\). An upper bound is assigned to each \(m\)-multitree. It is shown that for an \(m\)-multitree an \((m+1)\)-multitree can be constructed such that the upper bound assigned to it is at least as good as the one assigned to the original \(m\)-multitree. The author presents an algorithm to find an \(m\)-multitree bound base on \(P(A_{k_1})\) \((1\leq k_1\leq n)\), \(P(A_{k_1}\cap A_{k_2})\) \((1\leq k_1< k_2\leq n)\) and \(O(n)P(A_{k_1}\cap\cdots\cap A_{k_i})\) (\(1\leq k_1<\cdots< k_i\leq n\), \(i= 1,3,\dots, m+1\)) out of all \(O(n^{m+1})\) numbers. Lower bounds for the multivariate normal distribution function values are also presented as examples.