Title: Bounds on the Probability of the Union of Events
Speaker: Kunikazu Yoda, CCICADA/DIMACS
Date: Tuesday, February 11, 2014 11:00am - 12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Computing the probability of the union of events is important in sciences concerned with stochastic systems. Although the classical inclusion-exclusion principle gives the exact probability, the formula is impractical if the number of events is large due to an exponential number of terms involved. However, we can compute upper and lower bounds on the probability by using only part of the terms about intersections of small numbers of events, as in Bonferroni inequalities. The closed form bounds for small orders and solution to the binomial moment problem can give optimal bounds when only aggregated information about the part of the terms are available. The best bounds can be given by solving the Boolean probability bounding scheme, which uses the full disaggregated information about the part of the terms, although it requires an exponential number of variables. We present a relaxation of the scheme that uses the same disaggregated information while requiring only a polynomial number of variables. We also show a technique to reduce the size of the problem if some intersections of small numbers of events are empty.
This is work in progress, joint with Prof. Andras Prekopa of Rutgers University.