Probability bounds for $n$ random events under $(n-1)$-wise independence

Abstract

A collection of $n$ random events is said to be $(n-1)$-wise independent if any $n-1$ events among them are mutually independent. We characterise all probability measures with respect to which $n$ random events are $(n-1)$-wise independent. We provide sharp upper and lower bounds on the probability that at least $k$ out of $n$ events with given marginal probabilities occur over these probability measures. The bounds are shown to be computable in polynomial time.

18 pages, 2 tables