Hypergeometric tail inequalities: ending the insanity

By Matthew Skala. 2013

97 citations recorded by the source corpus.

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^2n}$ and $Pr[i \le E[i]-tn] \le e^{-2t^2n}$.

Subfields: Theoretical Computer Science

View Paper: https://www.semanticscholar.org/paper/abc9ee0d2cbfaf820a978d0657b1f8dadbe184fc

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Theoretical Computer Science

Citations in the corpus

Scalable Bias-Resistant Distributed Randomness (2017, methodology): “For a single group we start with Chvátal’s formula [55]”
Submodular Maximization in Clean Linear Time (2020, unknown): “and the distribution of R is hyper-geometric, we get by Inequality (10) in [58] (developed based on the works of [10, 29]) that Pr[|R ∩ S| ≥ h] = Pr[|R ∩ S| ≥ E[|R ∩ S|] + h− βk] ≤ e−2((h−βk)/k)2·k = e−2(h−βk)2/k .”