Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Graph-based upper bounds for the probability of the union of events. | Graph-based upper bounds for the probability of the union of events Pierangela Veneziani Mathematics Department SUNY College at Brockport 350 New Campus Drive Brockport Ny us pvenezia@ Submitted Nov 27 2007 Accepted Jan 28 2008 Published Feb 11 2008 Mathematics Subject Classifications 60E15 90C05 Abstract We consider the problem of generating upper bounds for the probability of the union of events when the individual probabilities of the events as well as the probabilities of pairs of these events are known. By formulating the problem as a Linear Program we can obtain bounds as objective function values corresponding to dual basic feasible solutions. The new upper bounds are based on underlying bipartite and threshold type graph structures. 1 Introduction The Boolean probability bounding problem can be formulated as follows let A1 . An be a finite set of arbitrary events in a probability space e and let us assume that the individual probabilities P Ai i 1 . n as well as the probabilities P I Pl Ail 1 i1 . ii n l 2 . m of up to m-tuples of these events are known where m n. Using this information we want to generate upper and lower bounds for the probability of a Boolean function of these events. The integer m is usually referred to as the degree of these bounds. The Boolean probability bounding scheme is a particular instance of the optimization version of the probabilistic satisfiability PSAT problem. The decision version of PSAT consists in determining whether given the probabilities that m logical sentences defined The author wishes to thank Dr. E. Boros for his continued support and her daughter Sofia for inspiration. The author would also like to acknowledge the work of the reviewer of the manuscript. THE ELECTRONIC JOURNAL OF COMBINATORICS 15 2008 R28 1 on n logical variables are true such probability assignment is consistent. The optimization version of PSAT in concerned with determining bounds on the probability that an additional sentence is .
