Abstract
We present new results on bounding the probability of a finite union of events, equation for a fixed positive integer N, using partial information on the events joint probabilities. We first consider bounds that are established in terms of {P(Ai)} and {ΣjcjP(Ai ∩ Aj)} where c1,⋯, cN are given weights. We derive a new class of lower bounds of at most pseudo-polynomial computational complexity. This class of lower bounds generalizes the recent bounds in [1], [2] and can be tighter in some cases than the Gallot-Kounias [3]-[5] and Prékopa-Gao [6] bounds which require more information on the events probabilities. We next consider bounds that fully exploit knowledge of {P(Ai)} and {P(Ai ∩ Aj)}. We establish new numerical lower/upper bounds on the union probability by solving a linear programming problem with equation variables. These bounds coincide with the optimal lower/upper bounds when N ≤ 7 and are guaranteed to be sharper than the optimal lower/upper bounds of [1], [2] that use {P(Ai)} and {Σj P(Ai ∩ Aj)}.
Original language | English |
---|---|
Title of host publication | Proceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015 |
Number of pages | 5 |
Publisher | Institute of Electrical and Electronics Engineers Inc. |
Publication date | 28 Sep 2015 |
Pages | 1761-1765 |
Article number | 7282758 |
ISBN (Electronic) | 9781467377041 |
DOIs | |
Publication status | Published - 28 Sep 2015 |
Externally published | Yes |
Event | IEEE International Symposium on Information Theory, ISIT 2015 - Hong Kong, Hong Kong Duration: 14 Jun 2015 → 19 Jun 2015 |
Conference
Conference | IEEE International Symposium on Information Theory, ISIT 2015 |
---|---|
Country/Territory | Hong Kong |
City | Hong Kong |
Period | 14/06/2015 → 19/06/2015 |
Sponsor | Information Theory Society of the Institute of Electrical and Electronics Engineers |
Series | IEEE International Symposium on Information Theory - Proceedings |
---|---|
Volume | 2015-June |
ISSN | 2157-8095 |
Bibliographical note
Funding Information:This work was supported in part by NSERC of Canada.
Publisher Copyright:
© 2015 IEEE.
Keywords
- communication systems
- linear programming
- probability of error analysis
- Union probability
- upper and lower bounds