On lower bounds for hypergeometric tails

Christos Pelekis; Jianhang Ai

arxiv: 2601.09485 · v2 · submitted 2026-01-14 · 🧮 math.PR

On lower bounds for hypergeometric tails

Jianhang Ai , Christos Pelekis This is my paper

Pith reviewed 2026-05-16 14:17 UTC · model grok-4.3

classification 🧮 math.PR

keywords hypergeometric distributiontail boundslower boundssampling without replacementmean absolute deviationconditional expectationvariance boundsprobability inequalities

0 comments

The pith

Hypergeometric random variables satisfy P(H ≥ E(H)) ≥ k/n when the population size n is at least eight times the sample size k.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves explicit lower bounds on the probability that a hypergeometric random variable meets or exceeds its expectation. Hypergeometric variables arise in sampling without replacement, so these bounds quantify how likely it is to see at least the average number of successes under finite-population constraints. One result gives the simple guarantee of at least k/n whenever n is eight or more times k. A second result supplies a tighter expression involving the variance, valid when the expectation lies in a restricted interior range and a mild inequality on the remaining population holds. Supporting lemmas bound the tail conditional expectation from above and the mean absolute deviation from below.

Core claim

Let n and k be positive integers with n ≥ k, and let H count the black marbles drawn in a sample of size k from an urn containing i black marbles out of n total. Then P(H ≥ E(H)) ≥ k/n whenever n ≥ 8k. Moreover, when 1 ≤ E(H) ≤ min{i, k} − 1 and (n − i)(n − k)/n > 1, the probability satisfies P(H ≥ E(H)) ≥ (e^{-1/12}/(4√2)) ⋅ √((n − 1)/n) ⋅ √Var(H) / (1 + √(1 + ((n − 1)/(n − k)) ⋅ Var(H))).

What carries the argument

Lower bounds on the hypergeometric upper tail probability obtained via an auxiliary upper bound on the tail conditional expectation and a lower bound on the mean absolute deviation.

If this is right

When the sample size is at most one-eighth the population size, the chance of observing at least the expected number of successes is bounded below by the sampling fraction k/n.
Under interior-mean conditions the probability can be bounded from below by a multiple of the standard deviation scaled by a simple function of the variance.
An upper bound on the conditional expectation of H given H ≥ E(H) holds for the hypergeometric family.
A lower bound on the mean absolute deviation of H is available for the same family.
The auxiliary bounds may be applied independently to other tail or deviation analyses of sampling-without-replacement distributions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same technique of controlling the tail conditional expectation could be tested on the binomial distribution to see whether analogous constants emerge.
Relaxing the n ≥ 8k threshold slightly might still preserve a comparable fractional lower bound, which could be checked by exhaustive computation for moderate k.
The explicit variance form suggests a possible route to concentration inequalities that remain valid even when the population is only modestly larger than the sample.
These lower bounds on the median-crossing probability may help calibrate error rates in combinatorial algorithms that rely on hypergeometric sampling.

Load-bearing premise

The condition n ≥ 8k for the first bound, and the restrictions 1 ≤ E(H) ≤ min{i,k} − 1 together with (n − i)(n − k)/n > 1 for the second bound.

What would settle it

A concrete numerical counterexample with n = 8k, any valid i, where direct enumeration shows P(H ≥ E(H)) < k/n would disprove the first claim; similarly, any triple satisfying the second set of conditions where the displayed inequality fails would disprove the refined bound.

read the original abstract

Let $n,k$ be positive integers such that $n\geq k$, and let $H$ be a hypergeometric random variable counting the number of black marbles in a sample without replacement of size $k$ from an urn that contains $i\in \{1,\ldots, n\}$ black and $n - i$ white marbles. It is shown that \[ \mathbb{P}(H \ge \mathbb{E}(H)) \ge k/n\, , \, \text{when} \,\, n\ge 8k \, . \] Furthermore, provided that $1\le \mathbb{E}(H)\le \min\{i,k\}-1$ as well as that $\frac{(n-i)(n-k)}{n}>1$, it is shown that \[ \mathbb{P}(H\ge \mathbb{E}(H)) \,\ge\, \frac{e^{-1/12}}{4\sqrt{2}} \cdot \sqrt{\frac{n-1}{n}} \cdot\frac{ \sqrt{\text{Var}(H)} }{1 + \sqrt{1+ \frac{n-1}{n-k}\cdot\text{Var}(H)}}\, . \] Auxiliary results which may be of independent interest include an upper bound on the tail conditional expectation and a lower bound on the mean absolute deviation of the hypergeometric distribution.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives two explicit lower bounds on P(H ≥ E(H)) for hypergeometric H, one simple and one variance-linked, plus some auxiliary tail and MAD bounds that look independently usable.

read the letter

The main results are a lower bound of k/n on the probability that the hypergeometric count meets or exceeds its mean when n is at least 8k, and a second bound that scales with sqrt(Var(H)) under conditions keeping the mean away from the edges and the sampling fraction small. The auxiliary upper bound on tail conditional expectation and lower bound on mean absolute deviation are presented as separate contributions and appear to support the main inequalities directly from distribution properties and standard tools like variance calculations or basic inequalities. No fitted parameters or circular steps show up in the claims. The explicit constants and the variance form are the clearest additions relative to usual hypergeometric concentration results. The conditions are stated clearly, which is helpful for knowing the regime. The main limitation is how restrictive those conditions are: n ≥ 8k forces a small sampling fraction, and the second bound needs 1 ≤ E(H) ≤ min(i,k)-1 plus (n-i)(n-k)/n >1. These avoid boundary problems but exclude many practical cases where k is comparable to n/2 or the mean sits near zero or the upper limit. The derivations seem internally consistent from the abstract and stress-test notes, with no visible contradictions or post-hoc adjustments. This work is aimed at people who need concrete, non-asymptotic tail lower bounds for hypergeometric sampling in discrete probability or applications like finite-population inference. It is narrow but the explicit forms and auxiliaries give it value for someone already working in that area. I would send it to peer review because the claims are grounded enough and the auxiliaries add something reusable, even if revisions will likely tighten the conditions or add examples.

Referee Report

2 major / 2 minor

Summary. The paper establishes two explicit lower bounds on P(H ≥ E(H)) for a hypergeometric random variable H ~ Hypergeometric(n, i, k). The first states that P(H ≥ E(H)) ≥ k/n whenever n ≥ 8k. The second, under the restrictions 1 ≤ E(H) ≤ min{i,k}−1 and (n−i)(n−k)/n > 1, gives P(H ≥ E(H)) ≥ (e^{−1/12}/(4√2)) ⋅ √((n−1)/n) ⋅ √Var(H) / (1 + √(1 + ((n−1)/(n−k)) Var(H))). Auxiliary results include an upper bound on the tail conditional expectation E[H | H ≥ E(H)] and a lower bound on the mean absolute deviation E[|H − E(H)|].

Significance. If the derivations hold, the results supply concrete, non-asymptotic lower bounds on the central probability mass of the hypergeometric distribution under explicit sampling-fraction restrictions. Such bounds are useful in combinatorial probability, sampling theory, and algorithmic applications where one needs guaranteed mass away from the lower tail without asymptotic approximations. The auxiliary bounds on conditional expectation and MAD are stated in closed form and may be reusable in other hypergeometric analyses.

major comments (2)

[§3, Theorem 1] §3, proof of Theorem 1: the derivation of the factor 8 in the hypothesis n ≥ 8k proceeds from the inequality E[H | H ≥ E(H)] ≤ E(H) + 1/2 together with a crude estimate on the MAD; the resulting constant appears loose and the proof does not indicate whether a smaller multiplier (e.g., n ≥ 4k) can be recovered by tightening the MAD lower bound.
[§4, (12)] §4, display (12): the second main inequality is obtained by combining the MAD lower bound with a one-sided Chebyshev-type estimate; the factor (n−1)/(n−k) inside the square root is introduced without an explicit justification that it remains bounded under the stated hypothesis (n−i)(n−k)/n > 1, which could affect the numerical sharpness of the constant e^{−1/12}/(4√2).

minor comments (2)

[Abstract] Abstract, second displayed inequality: the placement of the square-root term √((n−1)/n) is slightly ambiguous in the LaTeX; it should be clarified that it multiplies the entire fraction involving √Var(H).
[§2] §2, notation paragraph: the range of i is stated as {1,…,n} but the later conditions require i ≥ E(H) + 1; a single sentence reconciling the global parameter range with the local hypotheses would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We respond to each major comment below.

read point-by-point responses

Referee: [§3, Theorem 1] §3, proof of Theorem 1: the derivation of the factor 8 in the hypothesis n ≥ 8k proceeds from the inequality E[H | H ≥ E(H)] ≤ E(H) + 1/2 together with a crude estimate on the MAD; the resulting constant appears loose and the proof does not indicate whether a smaller multiplier (e.g., n ≥ 4k) can be recovered by tightening the MAD lower bound.

Authors: The factor of 8 is obtained by substituting the bound E[H | H ≥ E(H)] ≤ E(H) + 1/2 into the relation between the central probability and the MAD lower bound. The referee correctly notes that this choice is conservative. Our MAD lower bound is already stated in closed form for potential reuse, and tightening it further would require additional assumptions not present in the theorem. We will add a remark after Theorem 1 noting that the constant 8 is sufficient under the given hypotheses but may not be sharp, and that numerical evidence suggests n ≥ 4k often holds though it is not recovered by the current proof technique. revision: partial
Referee: [§4, (12)] §4, display (12): the second main inequality is obtained by combining the MAD lower bound with a one-sided Chebyshev-type estimate; the factor (n−1)/(n−k) inside the square root is introduced without an explicit justification that it remains bounded under the stated hypothesis (n−i)(n−k)/n > 1, which could affect the numerical sharpness of the constant e^{−1/12}/(4√2).

Authors: The factor (n−1)/(n−k) enters through the exact variance formula Var(H) = k(i/n)((n−i)/n)(n−k)/(n−1) when the one-sided Chebyshev inequality is applied to the MAD. The hypothesis (n−i)(n−k)/n > 1 guarantees that the denominator in the final bound is positive and that Var(H) is sufficiently large, but we agree an explicit sentence justifying the appearance and boundedness of the factor was omitted. We will revise the proof of the second bound to insert a short paragraph deriving the factor from the variance expression and confirming that the numerical constant e^{−1/12}/(4√2) remains valid under the stated restrictions. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper establishes lower bounds on P(H ≥ E(H)) for the hypergeometric distribution H by applying standard tail inequalities, conditional expectation bounds, and mean absolute deviation estimates under explicitly stated restrictions (n ≥ 8k; 1 ≤ E(H) ≤ min{i,k}-1 and (n-i)(n-k)/n > 1). These steps rely on distribution properties and classical inequalities rather than any self-definitional reduction, fitted parameters renamed as predictions, or load-bearing self-citations. The auxiliary results are derived independently and directly support the main claims without circularity. The derivation chain is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The derivations rest on the standard definition and moment formulas of the hypergeometric distribution together with basic probability inequalities; no free parameters are fitted and no new entities are introduced.

axioms (2)

standard math Hypergeometric distribution has the stated mean and variance formulas
Invoked to express E(H) and Var(H) in the bounds.
standard math Standard tail and deviation inequalities for discrete random variables
Used to obtain the explicit constants in the lower bounds.

pith-pipeline@v0.9.0 · 5529 in / 1267 out tokens · 39186 ms · 2026-05-16T14:17:16.188981+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction (8-tick period) reality_from_one_distinction echoes

?

echoes
ECHOES: this paper passage has the same mathematical shape or conceptual pattern as the Recognition theorem, but is not a direct formal dependency.

P(H≥E(H))≥k/n , when n≥8k

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages

[1]

Aydinian, V

H. Aydinian, V . Blinovsky,A Remark on the Problem of Nonnegative k-Sums, Problems of Inform. Trans- mission48(4) (2012) 56–61

work page 2012
[2]

Berend, A

D. Berend, A. Kontorovich,A sharp estimate of the binomial mean absolute deviation, Statistics & Probabil- ity Letters83(2013) 1254–1259

work page 2013
[3]

Broman, T

E. Broman, T. van de Brug, W. Kager, R. Meester,Stochastic domination and weak convergence of conditioned Bernoulli random variables, ALEA Latin Amer. J. Probab. Math. Stat.9(2) (2012) 403–434

work page 2012
[4]

J. N. Cooper and R. B. Ellis,Linearly bounded liars, adaptive covering codes, and deterministic random walks, J. Comb.1(2010) 307–334

work page 2010
[5]

Diaconis, S

P . Diaconis, S. Zabell,Closed form summation for classical distributions: variations on a theme of de Moivre, Statistical Science6(3) (1991) 284–302

work page 1991
[6]

Doerr,An elementary analysis of the probability that a binomial random variable exceeds its expectation, Statistics & Probability Letters139(2018) 67–74

B. Doerr,An elementary analysis of the probability that a binomial random variable exceeds its expectation, Statistics & Probability Letters139(2018) 67–74

work page 2018
[7]

Ehm,Binomial approximation to the Poisson binomial distribution, Statistics & Probability Letters11(1) (1991) 7–16

W. Ehm,Binomial approximation to the Poisson binomial distribution, Statistics & Probability Letters11(1) (1991) 7–16

work page 1991
[8]

Greenberg and M

S. Greenberg and M. Mohri,Tight lower bound on the probability of a binomial exceeding its expectation, Statistics & Probability Letters86(2014) 91–98. 13

work page 2014
[9]

Hui, C.J

S. Hui, C.J. ParkThe Representation of Hypergeometric Random Variables using Independent Bernoulli Ran- dom Variables, Communications in Statistics – Theory and Methods, 43(19) (2014) 4103–4108

work page 2014
[10]

Jogdeo, S

K. Jogdeo, S. Samuels,Monotone convergence of binomial probabilities and a generalisation of Ramanujan’s equation, The Annals of Mathematical Statistics39(4) (1968) 1191–1195

work page 1968
[11]

Klenke, L

A. Klenke, L. Mattner,Stochastic ordering of classical discrete distributions, Advances in Applied Proba- bility42(2) (2010) 392–410

work page 2010
[12]

Mattner, J

L. Mattner, J. Schulz,On normal approximations to symmetric hypergeometric laws, Transactions of the American Mathematical Society,370(1) (2018) 727–748

work page 2018
[13]

Pelekis, J

C. Pelekis, J. Ramon,A lower bound on the probability that a binomial random variable is exceeding its mean, Statistics & Probability Letters119(2016) 305–309

work page 2016
[14]

Pinelis,Best lower bound on the probability of a binomial exceeding its expectation, Statistics & Probability Letters179(2021) 109224

I. Pinelis,Best lower bound on the probability of a binomial exceeding its expectation, Statistics & Probability Letters179(2021) 109224

work page 2021
[15]

Pokrovskiy,A linear bound on the Manickam–Mikl´ os–Singhi conjecture, J

A. Pokrovskiy,A linear bound on the Manickam–Mikl´ os–Singhi conjecture, J. Combin. Theory Ser. A,133 (2015) 280–306

work page 2015
[16]

T. A. Ramasubban,The mean difference and the mean deviation of some discontinuous distributions, Biometrika,45(3/4) (1958) 549–556

work page 1958
[17]

Robbins,A Remark on Stirling’s Formula, The American Mathematical Monthly,62(1) (1955) 26–29

H. Robbins,A Remark on Stirling’s Formula, The American Mathematical Monthly,62(1) (1955) 26–29

work page 1955
[18]

Shaked, G.J

M. Shaked, G.J. Shanthikumar,Stochastic Orders, Springer, New York, 2007

work page 2007
[19]

Siegel,Median bounds and their application, Journal of Algorithms38(1) (2001) 184–236

A. Siegel,Median bounds and their application, Journal of Algorithms38(1) (2001) 184–236

work page 2001
[20]

Uhlmann,Vergleich der hypergeometrischen mit der binomial-verteilung, Metrika10(1966) 145–158

W. Uhlmann,Vergleich der hypergeometrischen mit der binomial-verteilung, Metrika10(1966) 145–158

work page 1966
[21]

Vatutin, V .G Mikhailov, (1983).Limit theorems for the number of empty cells in an equiprobable scheme for group allocation of particles, Theory Probab

V .A. Vatutin, V .G Mikhailov, (1983).Limit theorems for the number of empty cells in an equiprobable scheme for group allocation of particles, Theory Probab. Appl.27(1983) 734–743. Russian original in Teor. Veroy- atnost. i Primenen.27(1982) 684–692. 14

work page 1983

[1] [1]

Aydinian, V

H. Aydinian, V . Blinovsky,A Remark on the Problem of Nonnegative k-Sums, Problems of Inform. Trans- mission48(4) (2012) 56–61

work page 2012

[2] [2]

Berend, A

D. Berend, A. Kontorovich,A sharp estimate of the binomial mean absolute deviation, Statistics & Probabil- ity Letters83(2013) 1254–1259

work page 2013

[3] [3]

Broman, T

E. Broman, T. van de Brug, W. Kager, R. Meester,Stochastic domination and weak convergence of conditioned Bernoulli random variables, ALEA Latin Amer. J. Probab. Math. Stat.9(2) (2012) 403–434

work page 2012

[4] [4]

J. N. Cooper and R. B. Ellis,Linearly bounded liars, adaptive covering codes, and deterministic random walks, J. Comb.1(2010) 307–334

work page 2010

[5] [5]

Diaconis, S

P . Diaconis, S. Zabell,Closed form summation for classical distributions: variations on a theme of de Moivre, Statistical Science6(3) (1991) 284–302

work page 1991

[6] [6]

Doerr,An elementary analysis of the probability that a binomial random variable exceeds its expectation, Statistics & Probability Letters139(2018) 67–74

B. Doerr,An elementary analysis of the probability that a binomial random variable exceeds its expectation, Statistics & Probability Letters139(2018) 67–74

work page 2018

[7] [7]

Ehm,Binomial approximation to the Poisson binomial distribution, Statistics & Probability Letters11(1) (1991) 7–16

W. Ehm,Binomial approximation to the Poisson binomial distribution, Statistics & Probability Letters11(1) (1991) 7–16

work page 1991

[8] [8]

Greenberg and M

S. Greenberg and M. Mohri,Tight lower bound on the probability of a binomial exceeding its expectation, Statistics & Probability Letters86(2014) 91–98. 13

work page 2014

[9] [9]

Hui, C.J

S. Hui, C.J. ParkThe Representation of Hypergeometric Random Variables using Independent Bernoulli Ran- dom Variables, Communications in Statistics – Theory and Methods, 43(19) (2014) 4103–4108

work page 2014

[10] [10]

Jogdeo, S

K. Jogdeo, S. Samuels,Monotone convergence of binomial probabilities and a generalisation of Ramanujan’s equation, The Annals of Mathematical Statistics39(4) (1968) 1191–1195

work page 1968

[11] [11]

Klenke, L

A. Klenke, L. Mattner,Stochastic ordering of classical discrete distributions, Advances in Applied Proba- bility42(2) (2010) 392–410

work page 2010

[12] [12]

Mattner, J

L. Mattner, J. Schulz,On normal approximations to symmetric hypergeometric laws, Transactions of the American Mathematical Society,370(1) (2018) 727–748

work page 2018

[13] [13]

Pelekis, J

C. Pelekis, J. Ramon,A lower bound on the probability that a binomial random variable is exceeding its mean, Statistics & Probability Letters119(2016) 305–309

work page 2016

[14] [14]

Pinelis,Best lower bound on the probability of a binomial exceeding its expectation, Statistics & Probability Letters179(2021) 109224

I. Pinelis,Best lower bound on the probability of a binomial exceeding its expectation, Statistics & Probability Letters179(2021) 109224

work page 2021

[15] [15]

Pokrovskiy,A linear bound on the Manickam–Mikl´ os–Singhi conjecture, J

A. Pokrovskiy,A linear bound on the Manickam–Mikl´ os–Singhi conjecture, J. Combin. Theory Ser. A,133 (2015) 280–306

work page 2015

[16] [16]

T. A. Ramasubban,The mean difference and the mean deviation of some discontinuous distributions, Biometrika,45(3/4) (1958) 549–556

work page 1958

[17] [17]

Robbins,A Remark on Stirling’s Formula, The American Mathematical Monthly,62(1) (1955) 26–29

H. Robbins,A Remark on Stirling’s Formula, The American Mathematical Monthly,62(1) (1955) 26–29

work page 1955

[18] [18]

Shaked, G.J

M. Shaked, G.J. Shanthikumar,Stochastic Orders, Springer, New York, 2007

work page 2007

[19] [19]

Siegel,Median bounds and their application, Journal of Algorithms38(1) (2001) 184–236

A. Siegel,Median bounds and their application, Journal of Algorithms38(1) (2001) 184–236

work page 2001

[20] [20]

Uhlmann,Vergleich der hypergeometrischen mit der binomial-verteilung, Metrika10(1966) 145–158

W. Uhlmann,Vergleich der hypergeometrischen mit der binomial-verteilung, Metrika10(1966) 145–158

work page 1966

[21] [21]

Vatutin, V .G Mikhailov, (1983).Limit theorems for the number of empty cells in an equiprobable scheme for group allocation of particles, Theory Probab

V .A. Vatutin, V .G Mikhailov, (1983).Limit theorems for the number of empty cells in an equiprobable scheme for group allocation of particles, Theory Probab. Appl.27(1983) 734–743. Russian original in Teor. Veroy- atnost. i Primenen.27(1982) 684–692. 14

work page 1983