On Bounding the Union Probability Using Partial Weighted Information

2015/06/27 by Jun Yang, Fady Alajaji, Yang, Jun +3
Computer Science · Engineering · #Complexity and Algorithms in Graphs #Cryptography and Data Security #FOS: Mathematics #Probability (math.PR) #Wireless Communication Security Techniques

paper · pdf · doi:10.48550/arxiv.1506.08331

openalex publication_date 2015/06/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Effective bounds on the union probability are well known to be beneficial in the analysis of stochastic problems in many areas, including probability theory, information theory, statistical communications, computing and operations research. In this work we present new results on bounding the probability of a finite union of events, P(\bigcup_i=1^N A_i), for a fixed positive integer N, using partial information on the events in terms of \P(A_i)\ and \∑_j c_j P(A_i∩ A_j)\ where c₁, …, c_N are given weights. We derive two new classes of lower bounds of at most pseudo-polynomial computational complexity. These classes of lower bounds generalize the existing bound in \citeKuai2000 and recent bounds in \citeYang2014,Yang2014ISIT and are numerically shown to be tighter in some cases than the Gallot-Kounias bound \citeGallot1966,Kounias1968 and the Prékopa-Gao bound \citePrekopa2005 which require more information on the events probabilities.

Related

• A Short Survey on Bounding the Union Probability using Partial Information
• Lower Bounds on the Probability of a Finite Union of Events
• Improved Bounds on the Probability of a Union and on the Number of Events that Occur
• Estimates for probabilities of independent events and infinite series
• Partial results for union-closed conjectures on the weighted cube