Elementary Tail Bounds on the Hypergeometric Distribution

Marcos Curty; Vaisakh Mannalath; V\'ictor Zapatero

REVIEW 2 major objections 5 minor 1 cited by

Elementary Tail Bounds on the Hypergeometric Distribution

T0 review · 2 major / 5 minor · reviewed 2026-08-04 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Two new hypergeometric tail bounds, obtained by swapping the sample size and the number of marked items, depend on the sampling fraction and tighten the standard bounds whenever n > K.

desk verdict A small, honest paper giving elementary hypergeometric tail bounds; the symmetry-based bounds are useful for n > K, but Proposition 2 has a real gap that needs a one-line fix. read the letter →

arxiv 2510.19726 v2 pith:6JRVAEPJ submitted 2025-10-22 math.PR

Vaisakh Mannalath , Víctor Zapatero , Marcos Curty This is my paper · ORCID

classification math.PR MSC 60E1560C05

keywords hypergeometricdistributiontailboundssamplingwithoutreplacementconcentrationinequalitiesbinomialapproximationfactorialmomentspermutationsymmetrylargedeviations

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper establishes a simple but useful fact: because the hypergeometric distribution over (N,K,n) is unchanged when n and K are swapped, every upper tail bound known for the swapped variable is also a tail bound for the original one. That observation turns two sampling-fraction-blind bounds into bounds whose exponents and shapes depend on n/N. The first is an exponential bound with rate K times the relative entropy between 0/1 laws of parameters d/K and n/N; the second is a regularized incomplete beta bound with parameter n/N. In the regime n > K — sample larger than the number of marked items — both swapped bounds are tighter than the standard ones for the deviations tested, and the paper also derives a factorial-moment bound that is tighter still in the same numerical comparisons. This matters for users who need certificate-style tail limits for sampling without replacement and currently have to choose between loose fraction-blind exponential bounds or heavy existing alternatives.

What carries the argument

The key object is the symmetry of the hypergeometric distribution under exchange of the two parameters n and K: the variables X ~ Hypergeometric(N,K,n) and Z ~ Hypergeometric(N,n,K) have the same pmf, hence the same tail probabilities. This identity converts any upper bound for Z into a valid bound for X, and in the standard binomial-type bounds it replaces the trial count n by K and the success probability K/N by n/N, so the sampling fraction n/N appears explicitly. The second mechanism is the falling factorial (x)_{t+1} = x(x−1)⋯(x−t): with the exact factorial-moment identity E[(X)_{t+1}] = (K)_{t+1}(n)_{t+1}/(N)_{t+1}, Markov's inequality becomes a one-parameter infimum whose optimal t is

What would settle it

Set N=100, K=n=99, d=99. The paper's Proposition 2 formula gives t* = d, making the falling factor (d)_{d+1}=0 and the bound undefined, although the exact tail probability is 1. This single evaluation shows that the stated parameter range of the factorial-moment bound must be restricted or the t* rule modified.

Watch

Extended reading notes

Core claim

Proposition 1 is the load-bearing claim: for X ~ Hypergeometric(N,K,n) and any integer d ≥ nK/N + 1, the tail probability Pr[X ≥ d] is no larger than exp[−K D(d/K ‖ n/N)] and no larger than I_{n/N}(d, K−d+1), where D is the relative entropy between 0/1 laws and I is the regularized incomplete beta function. The proof is direct: Z ~ Hypergeometric(N,n,K) has the same probability mass function as X, so any upper bound on the tail of Z — for example the classical binomial-type bound applied to Z — transfers verbatim to X. The paper further proposes a factorial-moment bound, Proposition 2, selecting the number of falling-factorial factors t* by a ratio test; in the plotted regimes that bound is

Load-bearing premise

The factorial-moment bound rests on choosing t* = floor((Nd−Kn)/(N+d−(K+n))) without proving t* < d; when K and n are both close to N (e.g., N=100, K=n=99, d=99), the formula is undefined because (d)_{d+1}=0.

Editorial extensions

If this is right

When n > K, the swapped exponential bound and the swapped incomplete-beta bound are tighter than their standard counterparts for every integer deviation above the mean tested.
The new bounds scale with the sampling fraction: as n approaches N, the argument n/N moves closer to d/K and the bound reacts, instead of staying flat.
For rare marked items (small K) and large samples, the exponential bound has exponent proportional to K, which is what makes it practically useful.
The factorial-moment bound furnishes a strictly tighter alternative to the exponential bound for integer-valued nonnegative variables, with a closed-form ratio for choosing the number of factors.
Two additional distributional symmetries (sample complement and unmarked-count complement) extend the same tightening to parameters where n > N/2 or K > N/2.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A natural next step is to prove the observed dominance as a theorem: for every integer d ≥ nK/N + 1, the binomial with min(n,K) trials gives the tighter tail; a stochastic-ordering argument comparing Binomial(K, n/N) with Binomial(n, K/N) would settle it.
The symmetry trick is not tied to the two specific starting bounds; applying it to any existing sampling-without-replacement bound yields a new bound with n and K interchanged, and one can take the better of the pair in practice.
The undefined-edge case in Proposition 2 suggests a corrected statement with t* = min(floor((Nd−Kn)/(N+d−(K+n))), d−1); the ratio test still selects that value for all interior parameters.
In finite-population auditing and quality-certification settings, these bounds convert small-K large-n data into an explicit upper confidence certificate, which is exactly the regime where older bounds overstate risk.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

All you need to know: this is a small, clean paper that gives two hypergeometric tail bounds. The first is a reformulation of the Chernoff and Hoeffding bounds using the n–K symmetry; it is not a new inequality, but it adds the sampling-fraction dependence the standard Chernoff lacks. The second is a factorial-moment bound, a known technique applied to the hypergeometric case and worked out in closed form. That combination is useful, especially for n > K, and the paper is honest about what is new.

What's good: the proofs are transparent, the comparisons with the existing literature (Serfling, Hush-Scovel, Chatterjee, et al.) are fair, and the figures show genuine improvements in the high-sampling-fraction regime. The authors cite the relevant references, and there is no fitting or circular reasoning.

The main problem is in Proposition 2. The bound is derived by taking an infimum over 0 ≤ t < d, but the paper then chooses t* as the floor of (Nd−Kn)/(N+d−K−n) without proving that t* < d. It can be equal to d. For example, with N = 100, K = n = 90, d = 90, the floor is exactly 90, so the falling factorial in the denominator contains a zero term and the expression is undefined. The fix is to replace t* with min(floor(...), d−1). This is a real error in the proposition as stated, but it is minor in the sense that the method is correct and the corrected bound works. The authors need to fix this in revision.

One more thing: the claim that the factorial-moment bound is 'consistently tighter' than the Chernoff bounds is based only on the plots, not on a proof. That is acceptable in a short paper, but it would be good to state it as an empirical observation, not a theorem.

Bottom line: this paper is worth publishing after a modest revision. It is not a major result, but it is a solid reference for practitioners who need closed-form tail bounds. I would not desk reject it; it merits a serious referee. For a journal like Statistics & Probability Letters or similar, it's a reasonable fit. I'd cite it if I worked on hypergeometric tails.

Referee Report

2 major / 5 minor

Summary. The manuscript proposes elementary tail bounds for the hypergeometric distribution. Its main idea is to exploit the symmetry X ~ Hypergeometric(N,K,n) has the same law as Z ~ Hypergeometric(N,n,K), yielding Pr[X≥d] ≤ exp[-K D(d/K || n/N)] and Pr[X≥d] ≤ I_{n/N}(d, K-d+1). These bounds depend on the sampling fraction n/N, unlike the standard Chernoff and Hoeffding bounds. The paper also derives a factorial-moment bound, Pr[X≥d] ≤ (K)_{t*+1}(n)_{t*+1}/((N)_{t*+1}(d)_{t*+1}) with t* = floor((Nd-Kn)/(N+d-K-n)). The comparisons in Figures 1 and 2 illustrate the practical performance of the bounds against several existing inequalities.

Significance. If the stated results were valid without further qualification, the paper would contribute a simple, parameter-free method for obtaining sampling-fraction–dependent concentration bounds for the hypergeometric distribution. The symmetry trick is elegant and likely useful in applications such as quantum communication, and the factorial-moment bound is a natural addition. The derivations are transparent and rely on standard theorems (Chernoff, Hoeffding, Potts), with no fitted parameters. However, as written, both Proposition 1 and Proposition 2 contain missing parameter constraints that make the statements false or undefined in some nontrivial regimes. These are fixable but are load-bearing, so the main results need revision.

major comments (2)

[§2, Eq. (8) and Eq. (9), Proposition 1] The theorem states the bounds hold for every integer d ≥ nK/N + 1, with no upper limit. But Eq. (8) uses D(d/K || n/N), which is undefined when d > K because 1 - d/K is negative; Eq. (9) uses I_{n/N}(d, K-d+1), which is undefined when d > K (or at least requires d ≤ K). Since Z has only K trials, the Chernoff and beta bounds for Z require d ≤ K. Similarly, the original Chernoff and beta bounds in Eqs. (1) and (4) require d ≤ n. For d > min(K,n), the tail probability is 0 and a separate trivial bound applies. The proposition must state d ≤ K (and similarly d ≤ n for the unswapped forms) or treat these cases by the zero-tail remark.
[§2, Proposition 2, Eq. (17)] Proposition 2 is not valid as stated for all d ≥ nK/N + 1. The infimum in Eq. (13) is over 0 ≤ t < d, but the chosen t* = floor((Nd-Kn)/(N+d-K-n)) may equal or exceed d. For example, N=100, K=n=90, d=90 gives t*=90=d; the expression (K)_{91}(n)_{91}/((N)_{91}(d)_{91}) contains (90)_{91}=0 in numerator and denominator, so it is undefined. More generally t*≥d whenever (d-K)(d-n) ≤ 0. The fix is to set t* = min( floor((Nd-Kn)/(N+d-K-n)), d-1 ), and to prove that f(t) is minimized over [0,d) at this capped value. The paper currently omits this condition, so Proposition 2 is internally inconsistent.

minor comments (5)

[Introduction/§2] The claim that exploiting the symmetry is advantageous for n > K for all integer d is supported only by simulations, not by a proof. It should be phrased as an empirical observation or as a conjecture, and the same applies to the statement that the preferred bounding binomial is the one with the smaller number of trials.
[Introduction] The Hoeffding-based bound in Eq. (4) is cited to Hoeffding (1956) and Hui-Park (2014). Since the Poisson-binomial representation of the hypergeometric distribution is nontrivial, a brief reminder of the representation (or a precise reference) would help the reader verify the applicability.
[References] There are formatting errors in the reference list: the Rohde reference is missing a space and has '[149.3515-559', and the volume/page formatting is inconsistent (e.g., '149.3515-559').
[Figures 1 and 2] The green curve is described as the 'best-performing bound' among several listed inequalities, but the caption does not say which bound is used in each region or whether the minimum is taken pointwise. This should be clarified.
[Eq. (11)] The variable t in the infimum should be explicitly stated to be an integer, and the falling factorial notation should be defined in the main text (it is only used in the mention of Potts (1953)).

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: all bounds follow from external standard inequalities, exact permutation symmetry, and a classical factorial-moment identity; no fitted parameter or self-citation chain is load-bearing.

full rationale

The derivation chain is self-contained in the sense required by the circularity analysis. Proposition 1 uses only (i) the Chernoff inequality for hypergeometric variables (Hoeffding 1963, Chvátal 1979), (ii) Hoeffding's 1956 binomial-tail bound, and (iii) the exact symmetry Pr[X=k]=Pr[Z=k] for Z~Hypergeometric(N,n,K). The symmetry is an exact identity, not an ansatz, and the resulting bounds are not obtained by fitting any parameter to the data being bounded. Proposition 2 uses Markov's inequality with a falling-factorial test function and the exact factorial-moment identity E[(X)_{t+1}] = (K)_{t+1}(n)_{t+1}/(N)_{t+1} from Potts (1953). The ratio f(t+1)/f(t) then gives the candidate minimizer t*. No conclusion is assumed in its own proof, and no load-bearing step is justified only by a self-citation. The reader-identified issue that t* can equal d and fall outside the required range 0≤t<d is a genuine mathematical gap in the statement of Proposition 2, but it is a correctness/domain-condition problem, not circularity: the derivation does not presuppose the desired bound. The paper's numerical comparisons are illustrative simulations rather than fitted predictions, so they do not introduce circularity either.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

The paper relies entirely on known theorems and identities as lemmas; there are no fitted parameters or invented entities. The only questionable implicit assumption is that the optimal t* in Proposition 2 lies below d.

assumptions (7)

standard math Chernoff bound holds for hypergeometric random variables (Hoeffding 1963; Chvátal 1979).
Used in Eq. (1) as the baseline bound.
domain assumption A hypergeometric variable can be represented as a sum of n independent Bernoulli variables (Poisson binomial) with total mean nK/N (Hui and Park 2014).
Needed to apply Hoeffding's 1956 binomial tail bound in Eq. (4).
standard math Hoeffding's 1956 theorem bounds the Poisson binomial tail by I_{K/N}(d, n-d+1).
Gives Eq. (4).
standard math The hypergeometric PMF is symmetric under swapping n and K: Pr[X=k] = Pr[Z=k] for Z ~ Hypergeometric(N,n,K).
This combinatorial identity is the basis of Proposition 1.
standard math Factorial moments of the hypergeometric are E[(X)_r] = (K)_r (n)_r / (N)_r (Potts 1953).
Used in Eq. (12) to evaluate the Markov bound.
standard math The falling factorial φ(x) = (x)_{t+1} is non-decreasing and non-negative on non-negative integers for t < d.
Required for Markov's inequality in Eq. (10).
ad hoc to paper The chosen t* in Proposition 2 satisfies t* < d (implicitly assumed but not proved).
Needed for the falling factorial (d)_{t*+1} to be nonzero and for t* to lie in the infimum range; fails in extreme cases.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Elementary Tail Bounds on the Hypergeometric Distribution." pith.science (2026). https://pith.science/paper/6JRVAEPJ

@misc{pith2026251019726,
  author       = {Pith},
  title        = {Pith review of: Elementary Tail Bounds on the Hypergeometric Distribution},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6JRVAEPJ}},
  note         = {Machine review of arXiv:2510.19726}
}

read the original abstract

We use a simple method to derive two concentration bounds on the hypergeometric distribution. Comparison with existing results illustrates the advantage of these bounds across different regimes.

Figures

Figures reproduced from arXiv: 2510.19726 by the authors.

**Figure 1.** Upper tail probability, Pr[X ≥ n(K/N + δ)], as a function of the relative deviation δ with respect to the mean, for X ∼ Hypergeometric(N, K, n) and a population size N = 1000. Left column: K/N = 2%. Right column: K/N = 5%. Blue and yellow lines: Chernoff and β bounds with (solid) and without (dashed) invoking the permutation symmetry of n and K. Green line: best-performing bound among Serfling (1974), Hush and Scove… view at source ↗

**Figure 2.** Pr[X ≥ n(K/N + δ)] as a function of δ, for X ∼ Hypergeometric(N, K, n) and N = 10000. The followed criteria are common with those of [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Finite-key feasibility of geostationary quantum key distribution
quant-ph 2026-05 unverdicted novelty 5.0 of 10

Feasibility analysis of finite-key decoy-state BB84 QKD via GEO satellite downlink, evaluating rural/urban/coastal sites, multiple wavelengths, and cloud data to forecast secret-key rates and design guidelines.

Reference graph

Works this paper leans on

16 extracted references · cited by 1 Pith paper

[1]

Probability Inequalities for Sums of Bounded Random Variables.Journal of the American Statistical Association58, 13–30 (1963)

Hoeffding, W. Probability Inequalities for Sums of Bounded Random Variables.Journal of the American Statistical Association58, 13–30 (1963). Chvátal, V. The tail of the hypergeometric distribution.Discrete Mathematics25, 285-287 (1979)

1963
[2]

A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations.The Annals of Mathematical Statistics23, 493-507 (1952)

Chernoff, H. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations.The Annals of Mathematical Statistics23, 493-507 (1952)

1952
[3]

Finite sampling exponential bounds (Doctoral dissertation, University of Wash- ington, 2016)

Greene, E. Finite sampling exponential bounds (Doctoral dissertation, University of Wash- ington, 2016)

2016
[4]

Serfling, R. J. Probability inequalities for the sum in sampling without replacement.The Annals of Statistics2, 39-48 (1974)

1974
[5]

Concentration of the hypergeometric distribution.Statistics & Prob- ability Letters75, 127-132 (2005)

Hush, D., & Scovel, C. Concentration of the hypergeometric distribution.Statistics & Prob- ability Letters75, 127-132 (2005)

2005
[6]

Stein’s method for concentration inequalities.Probability Theory and Related Fields138, 305–321 (2007)

Chatterjee, S. Stein’s method for concentration inequalities.Probability Theory and Related Fields138, 305–321 (2007)

2007
[7]

Optimal calibration for multiple testing against local inhomogeneity in higher dimension.Probability theory and related fields149.3515-559 (2011)

Rohde, A. Optimal calibration for multiple testing against local inhomogeneity in higher dimension.Probability theory and related fields149.3515-559 (2011)

2011
[8]

Concentration inequalities via zero bias couplings.Statistics & Probability Letters86, 17-23 (2014)

Goldstein, L., & Işlak, Ü. Concentration inequalities via zero bias couplings.Statistics & Probability Letters86, 17-23 (2014)

2014

Show all 16 references

[9]

Bardenet, R., & Maillard, O. A. Concentrationinequalities for sampling without replacement. Bernoulli21,1361-1385 (2015)

2015
[10]

Greene, E., & Wellner, J. A. Exponential bounds for the hypergeometric distribution. Bernoulli: Official Journal of the Bernoulli Society for Mathematical Statistics and Prob- ability23, 1911 (2017)

1911
[11]

Probabilistic bounds on the coefficients of polynomials with only real zeros.J

Pitman, J. Probabilistic bounds on the coefficients of polynomials with only real zeros.J. Comb. Theory Ser. A77, 279 (1997)

1997
[12]

Hui, S., & Park, C. J. The representation of hypergeometric random variables using indepen- dent Bernoulli random variables.Communications in Statistics-Theory and Methods43, 4103-4108 (2014)

2014
[13]

On the distribution of the number of successes in independent trials.The Annals of Mathematical Statistics, 713-721 (1956)

Hoeffding, W. On the distribution of the number of successes in independent trials.The Annals of Mathematical Statistics, 713-721 (1956)

1956
[14]

K., & Nelson, R

Philips, T. K., & Nelson, R. The moment bound is tighter than Chernoff’s bound for positive tail probabilities.The American Statistician49, 175-178 (1995)

1995
[15]

Comparison between the Chernoff and factorial moment bounds for discrete random variables.The American Statistician51, 40-41 (1997)

Naveau, P. Comparison between the Chernoff and factorial moment bounds for discrete random variables.The American Statistician51, 40-41 (1997). 8

1997
[16]

Potts, R. B. Note on the factorial moments of standard distributions.Australian Journal of Physics6, 498-499 (1953). 9

1953

Pith tools

Reviewed August 4, 2026 · model on record in the stance chip above.

[1] [1]

Probability Inequalities for Sums of Bounded Random Variables.Journal of the American Statistical Association58, 13–30 (1963)

Hoeffding, W. Probability Inequalities for Sums of Bounded Random Variables.Journal of the American Statistical Association58, 13–30 (1963). Chvátal, V. The tail of the hypergeometric distribution.Discrete Mathematics25, 285-287 (1979)

1963

[2] [2]

A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations.The Annals of Mathematical Statistics23, 493-507 (1952)

Chernoff, H. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations.The Annals of Mathematical Statistics23, 493-507 (1952)

1952

[3] [3]

Finite sampling exponential bounds (Doctoral dissertation, University of Wash- ington, 2016)

Greene, E. Finite sampling exponential bounds (Doctoral dissertation, University of Wash- ington, 2016)

2016

[4] [4]

Serfling, R. J. Probability inequalities for the sum in sampling without replacement.The Annals of Statistics2, 39-48 (1974)

1974

[5] [5]

Concentration of the hypergeometric distribution.Statistics & Prob- ability Letters75, 127-132 (2005)

Hush, D., & Scovel, C. Concentration of the hypergeometric distribution.Statistics & Prob- ability Letters75, 127-132 (2005)

2005

[6] [6]

Stein’s method for concentration inequalities.Probability Theory and Related Fields138, 305–321 (2007)

Chatterjee, S. Stein’s method for concentration inequalities.Probability Theory and Related Fields138, 305–321 (2007)

2007

[7] [7]

Optimal calibration for multiple testing against local inhomogeneity in higher dimension.Probability theory and related fields149.3515-559 (2011)

Rohde, A. Optimal calibration for multiple testing against local inhomogeneity in higher dimension.Probability theory and related fields149.3515-559 (2011)

2011

[8] [8]

Concentration inequalities via zero bias couplings.Statistics & Probability Letters86, 17-23 (2014)

Goldstein, L., & Işlak, Ü. Concentration inequalities via zero bias couplings.Statistics & Probability Letters86, 17-23 (2014)

2014