This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Bukszár, J. Articles by Prékopa, A. Search for Related Content

Probability Bounds with Cherry Trees

Institute of Math., University of Miskolc, Miskolc-Egyetemváros, H-3515
RUTCOR, Rutgers University, 640 Bartholomew Road, Piscataway, NJ 08854-8003

A third order upper bound is presented on the probability of the union of a finite number of events, by means of graphs called cherry trees. These are graphs that we construct recursively in such a way that every time we pick a new vertex, connect it with two already existing vertices. If the latters are always adjacent, we call the cherry tree a t-cherry tree. A cherry tree has a weight that provides us with the upper bound on the union. Any Hunter-Worsley bound can be majorized by a t-cherry bound constructed by the use of the Hunter-Worsley tree. A cherry tree bound can be identified as a feasible solution to the dual of the Boolean probability bounding problem. A t-cherry tree bound can be identified as the objective function value of the dual vector corresponding to a dual feasible basis in the Boolean problem. This enables us to improve on the bound algorithmically, if we use the dual method of linear programming.

Key Words: Probability bounds; linear programming; hypergraphs; normal distribution
History: Received: May 7, 1999; revision received: August 25, 2000;