Show icon Show search tips...
Hide icon Hide search tips...

[CCICADA-announce] DIMACS/CCICADA Interdisciplinary Seminar Series - Tuesday, February 11, 2014

Linda Casals lindac at
Mon Feb 10 14:10:01 EST 2014


DIMACS/CCICADA Interdisciplinary Seminar Series Presents

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


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. 

DIMACS/CCICADA Interdisciplinary Series 

More information about the Dimacs-ccicada-announce mailing list