Text

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

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 a compact linear program. These bounds provide robust probability estimates when the assumption of conditional independence in a tree-structured graphical model is violated. We demonstrate, through numericals, the computational advantage of our compact linear program over alternate approaches. A comparison of bounds under various knowledge assumptions, such as univariate information and conditional independence, is provided. An application is illustrated in the context of Chow–Liu trees, wherein our bounds distinguish between various trees that encode the maximum possible mutual information.

Ketersediaan

Informasi Detail

Judul Seri

INFORMS JOURNAL ON OPTIMIZATION; Vol.3 No.1 Winter 2021

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 23 - 45

Bahasa

English

ISBN/ISSN

-

Klasifikasi

NONE

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

TREES
PROBABILITY BOUNDS
LINEAR OPTIMIZATION

Info Detail Spesifik

https://doi.org/10.1287/ijoo.2019.0038

Pernyataan Tanggungjawab

Divya Padmanabhan, Karthik Natarajan

Versi lain/terkait

Lampiran Berkas

Komentar