Closed Form Two-Sided Bounds for Probabilities that At Least r and Exactly r Out of n Events Occur

In two previous papers Prékopa (Prékopa, A. 1986a. Boole-Bonferroni inequalities and linear programming. Oper. Res.36 145–162; Prékopa, A. 1986b. Sharp bounds on probabilities using linear programming. To appear in Oper. Res.) gave algorithms to approximate probabilities that at least r and exactly r out of n events occur (1 ≤ r ≤ n). Primal and dual linear programming problems were formulated and solved by dual type algorithms. The purpose of the present paper is to give closed forms for the basis inverse and the corresponding dual vector in case of an arbitrary basis, furthermore to give closed forms for the lower and upper bounds, approximating the probability in question, in case of a dual feasible basis. In the case when the probability that at least one out of n events occurs is approximated, it is shown that the absolute values of the components of any dual vector form a monotonically decreasing sequence. The paper improves the method of inclusion-exclusion, proves new probability inequalities and proves the sharpness of some known inequalities.