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