Optimization Online


Tree Bounds for Sums of Bernoulli Random Variables: A Linear Optimization Approach

Divya Padmanabhan (divya_padmanabhan***at***sutd.edu.sg)
Karthik Natarajan (karthik_natarajan***at***sutd.edu.sg)

Abstract: We study the problem of computing the tightest upper and lower bounds on the probability that the sum of n dependent Bernoulli random variables exceeds an integer k. Under knowledge of all pairs of bivariate distributions denoted by a complete graph, the bounds are NP-hard to compute. When the bivariate distributions are specified on a tree graph, we show that tight bounds are computable in polynomial time using linear optimization. These bounds provide robust probability estimates when the assumption of conditional independence in a tree structured graphical model is violated. Generalization of the result to finding probability bounds of order statistic for more general random variables and instances where the bounds provide the most significant improvements over univariate bounds is also discussed in the paper.

Keywords: probability bounds, trees, linear optimization

Category 1: Robust Optimization

Category 2: Linear, Cone and Semidefinite Programming

Category 3: Combinatorial Optimization


Download: [PDF]

Entry Submitted: 10/12/2019
Entry Accepted: 10/12/2019
Entry Last Modified: 06/02/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society