Improved Bounds on the Probability of a Union and on the Number of Events that Occur

2025/05/18 by Ilan Adler, Richard M. Karp, Adler, Ilan +3
Mathematics · #Advanced Combinatorial Mathematics #Benford’s Law and Fraud Detection #Combinatorics (math.CO) #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Statistics Theory (math.ST)

paper · pdf · doi:10.48550/arxiv.2505.12243

openalex publication_date 2025/05/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let A₁, A₂, …, A_n be events in a sample space. Given the probability of the intersection of each collection of up to k+1 of these events, what can we say about the probability that at least r of the events occur? This question dates back to Boole in the 19th century, and it is well known that the odd partial sums of the Inclusion- Exclusion formula provide upper bounds, while the even partial sums provide lower bounds. We give a combinatorial characterization of the error in these bounds and use it to derive a very simple proof of the strongest possible bounds of a certain form, as well as a couple of improved bounds. The new bounds use more information than the classical Bonferroni-type inequalities, and are often sharper.

Related

• A Short Survey on Bounding the Union Probability using Partial Information
• Lower Bounds on the Probability of a Finite Union of Events
• On upper and lower bounds for probabilities of combinations of events
• On Bounding the Union Probability Using Partial Weighted Information
• Estimates for probabilities of independent events and infinite series