Tight Probability Bounds with Pairwise Independence

DOI10.1137/21M1408294zbMATH Open1524.60005arXiv2006.00516OpenAlexW3031093968MaRDI QIDQ6158360FDOQ6158360

Authors: Karthik Natarajan 

Publication date: 31 May 2023

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: While useful probability bounds for $n$ pairwise independent Bernoulli random variables adding up to at least an integer $k$ have been proposed in the literature, none of these bounds are tight in general. In this paper, we provide several results in this direction. Firstly, when $k=1$, the tightest upper bound on the probability of the union of $n$ pairwise independent events is provided in closed-form for any input marginal probability vector $mathbfpin[0,1{]}^n$. To prove the result, we show the existence of a positively correlated Bernoulli random vector with transformed bivariate probabilities, which is of independent interest. Building on this, we show that the ratio of the Boole union bound and the tight pairwise independent bound is upper bounded by $4/3$ and that the ratio is attained. Applications of the result in correlation gap analysis and distributionally robust bottleneck optimization are discussed. The result is extended to find the tightest lower bound on the probability of the intersection of $n$ pairwise independent events. Secondly, for any $kgeq2$ and input marginal probability vector $mathbfpin[0,1{]}^n$, new upper bounds are derived by exploiting ordering of probabilities. Numerical examples are provided to illustrate when the bounds provide improvement over existing bounds. Lastly, we identify specific instances when the existing and the new bounds are tight, for example, with identical marginal probabilities.

Full work available at URL: https://arxiv.org/abs/2006.00516

Recommendations

• A relative bound for independence
• Probability bounds for \(n\) random events under \((n-1)\)-wise independence
• scientific article; zbMATH DE number 437558
• Chernoff–Hoeffding Bounds for Applications with Limited Independence
• Independence, relative randomness, and PA degrees
• On the tightness of the \(\frac {5}{14}\) independence ratio
• Pairwise Independence and Derandomization
• Pairwise independence and derandomization.
• Sum of squares lower bounds from pairwise independence (extended abstract)

zbMATH Keywords

linear programmingboundspairwise independence

Mathematics Subject Classification ID

Computational methods for problems pertaining to probability theory (60-08) Linear programming (90C05) Inequalities; stochastic orderings (60E15) Combinatorial probability (60C05)

Cites Work

• Title not available (Why is that?)
• Probability Inequalities for Sums of Bounded Random Variables
• Title not available (Why is that?)
• Bonferroni inequalities
• Bounding the probability of the union of events by aggregation and disaggregation in linear programs
• Sharp Bounds on Probabilities Using Linear Programming
• A note on the background of several Bonferroni–Galambos-type inequalities
• A sharp upper probability bound for the occurrence of at least m out of n events
• Boole-Bonferroni Inequalities and Linear Programming
• Closed Form Two-Sided Bounds for Probabilities that At Least r and Exactly r Out of n Events Occur
• Best Linear Bonferroni Bounds
• Most Stringent Bounds on Aggregated Probabilities of Partially Specified Dependent Probability Systems
• Polynomially computable bounds for the probability of the union of events
• An Inequality for Probabilities
• Bounds for the Probability of a Union, with Applications
• Bottleneck extrema
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• Maximizing a monotone submodular function subject to a matroid constraint
• An upper bound for the probability of a union
• Chernoff–Hoeffding Bounds for Applications with Limited Independence
• A lower bound on the probability of a union
• On a set of almost deterministic k-independent random variables
• A lower bound on the probability of a finite union of events
• An improved Bonferroni inequality and applications
• Range of correlation matrices for dependent Bernoulli random variables
• A family of multivariate binary distributions for simulating correlated binary variables with specified marginal means and correlations
• Correlation polytopes: Their geometry and complexity
• Price of correlations in stochastic optimization
• Best Possible Inequalities for the Probability of a Logical Function of Events
• Miscellanea. A note on generating correlated binary variables
• Methods for Proving Bonferroni Type Inequalities
• On construction of \(k\)-wise independent random variables
• The maximal probability that \(k\)-wise independent bits are all 1
• Graph-based upper bounds for the probability of the union of events
• Non-Markovian Processes with the Semigroup Property
• Das maximale Signifikanzniveau des Tests: Lehne \(H_0\) ab, wenn \(k\) unter \(n\) gegebenen Tests zur Ablehnung führen
• Inequalities for the probability of the occurrence of at least m out of n events
• Strengthened bounds for the probability of \(k\)-out-of-\(n\) events
• Small deviations of sums of independent random variables
• Title not available (Why is that?)
• Optimality conditions for Hunter's bound
• Bivalent trees and forests or upper bounds for the probability of a union revisited
• Pairwise independent random variables
• Pairwise Statistical Independence
• Improved Bonferroni Inequalities and Binomially Bounded Functions
• Lower bounds on the probability of a finite union of events
• On Khintchine type inequalities for \(k\)-wise independent Rademacher random variables
• New upper bounds on the probability of events based on graph structures
• Improved bounds on the probability of the union of events some of whose intersections are empty
• Constructing Small Sample Spaces Satisfying Given Constraints
• Distributionally robust bottleneck combinatorial problems: uncertainty quantification and robust decision making
• Pairwise Independence of Jointly Dependent Variables
• On the joint entropy of \(d\)-wise-independent variables.
• EXACT LOWER BOUND ON AN ‘EXACTLY ONE’ PROBABILITY

Cited In (5)

• Pairwise Independence and Derandomization
• Chernoff–Hoeffding Bounds for Applications with Limited Independence
• Unimodality, independence lead to NP-hardness of interval probability problems
• Affinity in paired event probability
• Probability bounds for \(n\) random events under \((n-1)\)-wise independence

This page was built for publication: Tight Probability Bounds with Pairwise Independence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6158360)