Hypergeometric tail inequalities: ending the insanity

Abstract

The hypergeometric distribution is briefly and informally surveyed, including popular notation, symmetries, and the tail inequalities $Pr[i\ge E[i]+tn]\le e^{-2t^{2}n}$ and $Pr[i\le E[i]-tn]\le e^{-2t^{2}n}$.

5 pages

Cited by in corpus (14)

• Submodular Maximization Beyond Non-negativity: Guarantees, Fast Algorithms, and Applications
• Greed is Good: Near-Optimal Submodular Maximization via Greedy Optimization
• Sifting attacks in finite-size quantum key distribution
• Fair Coin Flipping: Tighter Analysis and the Many-Party Case
• A Generic Sample Splitting Approach for Refined Community Recovery in Stochastic Block Models
• Network Cross-Validation for Determining the Number of Communities in Network Data
• A Time-Efficient Quantum Walk for 3-Distinctness Using Nested Updates
• Superlinear subset partition graphs with dimension reduction, strong adjacency, and endpoint count
• Query K-means Clustering and the Double Dixie Cup Problem
• Maximizing Symmetric Submodular Functions
• $H{S}^2$: Active Learning over Hypergraphs
• The Normalized Matching Property in Random and Pseudorandom Bipartite Graphs
• An Almost-Optimally Fair Three-Party Coin-Flipping Protocol
• An elementary heuristic for Hardy-Littlewood extended Goldbach's conjecture