Tight Probability Bounds with Pairwise Independence

DOI10.1137/21m1408294zbMath1524.60005arXiv2006.00516OpenAlexW3031093968MaRDI QIDQ6158360

Unnamed Author, Karthik Natarajan

Publication date: 31 May 2023

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

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

zbMATH Keywords

linear programmingboundspairwise independence

Mathematics Subject Classification ID

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

Related Items (1)

Probability bounds for \(n\) random events under \((n-1)\)-wise independence

Cites Work

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

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