129. New algorithms for probability bounds with cherry trees
Invited abstract in session TD-3: Stochastic optimization and applications I, stream Stochastic optimization and applications.
Thursday, 14:45 - 16:15Room: C 104
Authors (first author is the speaker)
| 1. | Edith Kovács
|
| Analysis and Operations Research, Budapest University of Technology and Economics |
Abstract
Let A_1 … A_n be n arbitrary events in a probability space. The aim is to find upper bounds on the probability of the union events based on calculating only the probabilities of all the intersections of pairs and triplets of events from a dataset.
In [1] József Bukszár and András Prékopa proved that with the help of so-called cherry tree graphs, it is possible to give upper bounds on the union of events. They showed that by extending the tree structure, used for the Hunter-Worsley [2, 3] bound, to a cherry tree structure gives an upper bound at least as good as the Hunter-Worsley bound.
In the present talk, we exploit the fact that the so-called t-cherry trees used by Bukszár and Prékopa can be regarded also as junction trees. An alternative, equivalent definition of the weight of the cherry tree graph is given, based on which two new algorithms are presented and illustrated on examples.
[1] Bukszár, József, and Andras Prekopa. "Probability bounds with cherry trees." Mathematics of Operations Research 26.1 (2001): 174-192.
[2] Hunter, David. "An upper bound for the probability of a union." Journal of Applied Probability 13.3 (1976): 597-603.
[3] Worsley, K. J. "An improved Bonferroni inequality and applications." Biometrika 69.2 (1982): 297-302.
Keywords
- Optimization under uncertainty and applications
- Optimization for learning and data analysis
- Data driven optimization
Status: accepted
Back to the list of papers