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

Divya Padmanabhan, Karthik Natarajan

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 know…