Strengthened bounds for the probability of -out-of- events

详细信息    查看全文

• 作者：Feng Qiu ; ^{fqiu@gatech.edu" class="auth_mail" title="E-mail the corresponding author} ; Shabbir Ahmed ^{sahmed@isye.gatech.edu" class="auth_mail" title="E-mail the corresponding author} ; Santanu S. Dey ^{santanu.dey@isye.gatech.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Linear programming ; Probability bound ; kk-of-nn event
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：10 January 2016
• 年：2016
• 卷：198
• 期：Complete
• 页码：232-240
• 全文大小：392 K

文摘

Given a set of n$n$ random events in a probability space, represented by n$n$ Bernoulli variables (not necessarily independent), we consider the probability that at least k$k$ out of n$n$ events occur. When partial distribution information, i.e., marginal probabilities and all joint probabilities of up to $m(m<n)$ events, are provided, only an upper or lower bound can be computed for this probability. Recently Prékopa and Gao (2005) proposed a polynomial-size linear program to obtain strong bounds for the probability of union of events, i.e., k=1$k=1$. In this work, we propose inequalities that can be added to this linear program to strengthen the bounds. We also show that with a slight modification of the objective function this linear program and the inequalities can be used for the more general case where k$k$ is any positive integer less than or equal to n$n$. We use the strengthened linear program to compute probability bounds for the examples used by Prékopa and Gao, and the comparison shows significant improvement in the bound quality.