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

DOI10.1016/J.ORL.2023.01.004MaRDI QIDQ6161295zbMATH OpenOpenAlexFDO

Authors Karthik Natarajan, Colin Tan

Publication date 27 June 2023

Published in Operations Research Letters (Search for Journal in Brave)

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

zbMATH Keywords

\((n-1)\)-wise independenceBonferroni boundsmutual independenceprobabilistic methodprobability bounds

Mathematics Subject Classification ID

Axioms; other general questions in probability (60A05)

Abstract: A collection of $n$ random events is said to be $(n-1)$-wise independent if any $n-1$ events among them are mutually independent. We characterise all probability measures with respect to which $n$ random events are $(n-1)$-wise independent. We provide sharp upper and lower bounds on the probability that at least $k$ out of $n$ events with given marginal probabilities occur over these probability measures. The bounds are shown to be computable in polynomial time.

Recommendations

• Strengthened bounds for the probability of \(k\)-out-of-\(n\) events
• On extreme joint probabilities of k events chosen from n events
• Tight Probability Bounds with Pairwise Independence
• EXACT LOWER BOUND ON AN ‘EXACTLY ONE’ PROBABILITY
• Lower and upper bounds for the probability that at least r and exactly r out of n events occur

Cites work

• Asymptotic lower bounds for Ramsey functions
• Bounds for the Probability of a Union, with Applications
• Closed Form Two-Sided Bounds for Probabilities that At Least r and Exactly r Out of n Events Occur
• Counterexamples in probability.
• Das maximale Signifikanzniveau des Tests: Lehne \(H_0\) ab, wenn \(k\) unter \(n\) gegebenen Tests zur Ablehnung führen
• Dependent Random Variables with Independent Subsets
• Estimates for the Distribution Function of a Sum of Two Random Variables When the Marginal Distributions are Fixed
• scientific article; zbMATH DE number 53883 (Why is no real title available?)
• scientific article; zbMATH DE number 3492718 (Why is no real title available?)
• scientific article; zbMATH DE number 3249395 (Why is no real title available?)
• scientific article; zbMATH DE number 3026527 (Why is no real title available?)
• Mathematical risk analysis. Dependence, risk bounds, optimal allocations and portfolios
• On a problem of Spencer
• On computing the distribution function for the Poisson binomial distribution
• Pairwise Independence May Not Imply Independence: New Illustrations and a Generalization
• Tight Probability Bounds with Pairwise Independence

Cited in

(5)

• Revisit the Lovász local lemma
• scientific article; zbMATH DE number 1457406 (Why is no real title available?)
• Tight Probability Bounds with Pairwise Independence
• A combinatorial problem related to the classical probability
• Exact expressions for the maximal probability that all k-wise independent bits are 1

This page was built for publication: Probability bounds for \(n\) random events under \((n-1)\)-wise independence

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