  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.
