Sharp small-deviation inequalities for sums of independent nonnegative random variables

Guanyang Wang; Jun Yan; Peng Zhang; Weibo Fu; Yanjun Han; Zhengqing Zhou

REVIEW 2 major objections 3 minor 2 cited by

This paper proves a sharp lower bound for the probability that a sum of independent nonnegative random variables falls below its expected value plus a slack δ, confirming the e^{-1} conjecture for all δ≥1.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · deepseek-v4-flash

2026-07-31 23:22 UTC pith:RGUC6M4D

load-bearing objection A clean reduction that would settle Feige's conjecture for δ≥1, if the unproved Vlassis–Thomas calibration theorem holds—currently a conditional result. the 2 major comments →

arxiv 2607.23980 v1 pith:RGUC6M4D submitted 2026-07-27 math.PR math.CO

Sharp small-deviation inequalities for sums of independent nonnegative random variables

Weibo Fu , Yanjun Han , Guanyang Wang , Jun Yan , Peng Zhang , Zhengqing Zhou This is my paper

classification math.PR math.CO MSC 60E1552A40

keywords small deviationssums of nonnegative random variablese^{-1} conjecturesharp inequalityfirst moment boundsimplex calibrationhalfspace volumecentroid inequality

verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The paper establishes a sharp small-deviation inequality for sums of independent nonnegative random variables subject only to first-moment constraints. Specifically, if E X_i ≤ 1 and S = ∑ X_i, then the chance that S < E S + δ is at least b_{n,δ}, a closed-form expression that for δ≥1 never falls below e^{-1} and is exactly attained by a two-point distribution for every n. This settles a long-standing open conjecture in the range δ≥1 and provides the best possible universal constant. For the remaining range 0<δ<1, the paper obtains the explicit but weaker bound δ e^{-δ}. The proof reduces the probabilistic question to a volume estimate on the simplex via a calibration theorem for simplex-weighted sums.

Core claim

The central claim is Theorem 1.1: for independent nonnegative X_i with E X_i ≤ 1, the small-deviation probability P(S < E S + δ) is at least b_{n,δ} = δ(n/(n+δ))^n for 0<δ<1 and b_{n,δ} = (1 - 1/(n+δ))^n for δ≥1, with equality attained for every n and δ≥1. The proof has two independent ingredients. A calibration theorem, taken as an external input, states that for independent nonnegative variables with unit means, the function K_n(Y) = P_D(∑ Y_i D_i ≤ 1), where D is uniform on the standard simplex, is stochastically no smaller than uniform. The geometric ingredient bounds K_n(y) by 1 - b_{n,δ} whenever ∑ y_i ≥ n+δ, using the classical centroid inequality for convex bodies and its recent exte

What carries the argument

The key object is the function K_n(y) = P_D(∑ y_i D_i ≤ 1), with D uniform on the standard n-simplex. It serves as both a probability and a geometry: it is the normalized volume of a halfspace slice of the simplex, and it is a calibrated statistic for independent nonnegative random variables with unit means. The proof's machinery is the interplay between these two roles — the event {S ≥ E S + δ} is mapped to {K_n(Y) ≤ 1 - b_{n,δ}}, and the generalized centroid inequality bounds the volume of the corresponding slice from below. In effect, the problem becomes a convex-geometric one, with the calibration theorem supplying the final probabilistic step.

Load-bearing premise

The load-bearing premise is the calibration theorem taken as external input: for independent nonnegative variables with unit means, the simplex-weighted probability K_n(Y) satisfies P(K_n(Y) ≤ α) ≤ α for all α. If this fails, the final step of the proof collapses even though the geometric halfspace bound is correct.

What would settle it

Find independent nonnegative variables Y_i with E Y_i ≤ 1 and a number α∈(0,1) for which P(K_n(Y) ≤ α) exceeds α, where K_n uses the uniform simplex distribution. Such a counterexample would refute the calibration theorem and hence the paper's main inequality. The paper does not supply its own proof of the calibration theorem, so this is the most direct test.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

For every n and δ≥1, the inequality P(S < E S + δ) ≥ e^{-1} holds, matching the sharp constant; this confirms the e^{-1} conjecture in that range.
For δ≥1, the bound b_{n,δ} is optimal for each fixed n, as demonstrated by the two-point example that attains it.
For 0<δ<1, the paper establishes the explicit bound P(S < E S + δ) ≥ δ e^{-δ}, weaker than the conjectured min{δ/(1+δ), e^{-1}}.
The proof shows that the probabilistic inequality follows from a halfspace volume estimate for the simplex, so the result holds for any first-moment-constrained independent nonnegative variables.
The paper reports a fully formalized proof of the e^{-1} case, so the main argument can be checked mechanically.

Where Pith is reading between the lines

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

The gap between the new bound and the conjectured sharp bound in the range 0<δ<1 stems entirely from the geometric estimate; a tighter centroid-type inequality for halfspaces that do not contain the centroid would likely close the gap.
The two-point sharpness example for δ≥1 suggests that for δ<1 the extremal distribution may require more than two atoms; the paper's method gives no characterisation of the extremal law in that regime.
The calibration theorem at the core of the proof originates in distribution-free testing; read in that direction, the e^{-1} bound may translate into a finite-sample coverage guarantee for a nonparametric confidence interval, a consequence the paper leaves implicit.
Because the paper's main theorem inherits the calibration theorem as an unproved input, the result's full strength depends on that theorem's validity; any weakening of its hypotheses would extend the inequality to broader classes of random variables.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

A clean reduction that would settle Feige's conjecture for δ≥1, if the unproved Vlassis–Thomas calibration theorem holds—currently a conditional result.

read the letter

Short version: the paper gives a sharp small-deviation bound for sums of independent nonnegative variables and claims to prove Feige's conjecture for δ≥1. The internal math is clean and the reduction is elegant; the whole result, however, rests on a single external theorem stated without proof. Right now the paper is a conditional corollary of that theorem.

What is actually new: Theorem 1.1 states a sharp two-branch bound b_{n,δ}. The δ≥1 branch resolves Feige's conjecture with the optimal constant e^{-1}. Previous work only handled i.i.d. or log-concave cases or weaker constants. The sharpness construction is correct: a two-point distribution achieves the bound. The proof itself is a neat shift: Y_i = X_i + 1 - μ_i turns the event S ≥ E S + δ into ΣY_i ≥ n + δ, and then the Dirichlet calibration theorem plus the Letwin–Yaskin generalization of Grünbaum's inequality gives the bound. I checked the geometry: the support function computation h_K(-ξ) = (1/(n+1))Σy_i is right, the projection onto 1^⊥ is harmless, and the algebra matches Theorem 2.2 both for 0<δ<1 and δ≥1. No circularity or fitting anywhere; the citation pattern looks honest.

The soft spot, and it's a real one: Theorem 2.1 (Vlassis–Thomas) is a preprint posted 18 days before this one, and it is used as a black box with no proof. The final inequality is exactly P(K_n(Y) ≤ 1 - b_{n,δ}) ≤ 1 - b_{n,δ}; if that theorem has a hidden condition or is false, the whole result collapses. The Lean formalization is mentioned but no commit hash or artifact is provided, and it covers only δ=1. The authors need to supply a proof or a precise formal certificate for Theorem 2.1 before the result is usable. The Letwin–Yaskin theorem is less concerning—it's to appear in Israel J. Math.

The paper is a genuine contribution in outline, and deserves a serious referee. Send it out, but the referees should be asked to verify the Vlassis–Thomas theorem independently, and the authors should provide the missing proof or a machine-checkable version of it. Then, if it holds up, this is a major within-field result.

Reading group: maybe—worth discussing if someone wants to see the reduction. I wouldn't cite it in my own work until the external theorem is checked.

Referee Report

2 major / 3 minor

Summary. The paper claims a sharp small-deviation lower bound for sums of independent nonnegative random variables with mean at most one. For n≥1 and δ>0, it proves P(S<ES+δ) ≥ b_{n,δ}, with b_{n,δ}=δ(n/(n+δ))^n for 0<δ<1 and b_{n,δ}=(1-1/(n+δ))^n for δ≥1. Since b_{n,δ}≥e^{-1} for δ≥1, the paper claims Feige's conjecture is resolved in the affirmative for δ≥1. The proof shifts X_i to Y_i=X_i+1-μ_i, which are nonnegative with mean 1, then bounds a Dirichlet tail K_n(Y) geometrically via a generalized Grünbaum inequality, and finally applies an external calibration theorem of Vlassis and Thomas to convert the tail bound into a probability inequality. The sharpness example for δ≥1 is explicit and gives equality. The geometric part is internally sound, but the central probability inequality depends entirely on Theorem 2.1, which is stated without proof and cited to a preprint posted only 18 days before the manuscript.

Significance. If the external Theorem 2.1 is valid, this is an elegant and significant reduction: it settles Feige's conjecture for the entire range δ≥1, a long-standing open problem, and it also gives a new bound for 0<δ<1. The proof has several strengths: the centering shift Y_i=X_i+1-μ_i is natural and preserves the hypotheses; the support-function computation h_K(-ξ)=(1/(n+1))∑ y_i is correct; the projection of the shifted simplex to R^n is handled correctly; the algebra matching the two branches of Theorem 2.2 to b_{n,δ} checks out; and the sharpness example attains equality for all n and δ≥1. There is no evident circularity: the derivation does not use Feige's conjecture and no parameters are fitted to force the result. The paper does not itself contain a machine-checked proof; it references an external Lean formalization, but the artifact is not included in the submission. The decisive caveat is that Theorem 2.1 — the calibration theorem of Vlassis and Thomas — is used as a black box. The presented proof is therefore conditional on an unpublished, unpeer-reviewed external theorem.

major comments (2)

[Section 2.1 (Theorem 2.1) and Section 2.2] Theorem 2.1 is the load-bearing ingredient of the paper. In Section 2.2, the proof applies it with α=1-b_{n,δ} to conclude P(S≥ES+δ)≤1-b_{n,δ}. If Theorem 2.1 is false, or if it has an unstated support/continuity restriction, the final inequality (1.2) collapses, regardless of the correctness of the geometric estimate. The manuscript provides no proof of Theorem 2.1 and cites only [VT26], a preprint posted 18 days before this paper. For a serious journal, this is not sufficient for a central theorem whose statement is at least as strong as the paper's main result. The authors must include a self-contained proof of Theorem 2.1 in an appendix, or give a peer-reviewed reference, or provide a machine-checked certificate as part of the submission. Without this, the paper cannot independently claim to prove Feige's conjecture for δ≥1.
[Statement on AI use and abstract] The manuscript states that an accompanying Lean formalization 'provides an end-to-end formal proof of Feige's e^{-1} conjecture' and that the initial proof was found by ChatGPT 5.6 Pro. The Lean artifact is not included in the submission; only a URL is mentioned. If the formalization is intended to address the unproved status of Theorem 2.1, it must be supplied and its scope stated precisely, including which parts of the proof are formalized and which external theorems are assumed. As written, the claim about a machine-checked proof is not verifiable from the manuscript and should be either substantiated or removed.

minor comments (3)

[Abstract and Section 1] The sentence 'The proof is found by ChatGPT 5.6 Pro' is unusual and, if kept, should be moved to the AI-use statement rather than appearing in the abstract. The mathematical content is unaffected, but the wording is inappropriate for a formal research paper.
[References] The reference [VT26] is a preprint posted 9 July 2026, and [MRS+26] is posted 21 July 2026. These are very recent and not yet peer-reviewed. Please provide stable publication data when available, and for [LY24] cite the final journal version if it has appeared.
[Section 2.2] The geometric step is correct but quite compressed. The transition from the event {∑ y_iD_i ≥ (1/(n+δ))∑ y_i} to the halfspace intersection H_{(1-δ)/(n+δ),ξ} is not shown in detail. Adding two lines of algebra, and explicitly checking that α=(1-δ)/(n+δ) lies in the required range (-1,1/n) for all δ>0, would improve readability and make the proof easier to audit.

Circularity Check

0 steps flagged

No significant circularity: Theorem 1.1 is a direct combination of two external theorems, with no fitted parameters, self-citation chain, or definitional equivalence.

full rationale

The derivation chain is: (i) Vlassis–Thomas calibration theorem (Theorem 2.1, stated as an external input from [VT26]) gives P(K_n(Y)≤α)≤α; (ii) the Letwin–Yaskin generalization of Grünbaum's inequality (Theorem 2.2, also external) gives the geometric bound K_n(y)≤1−b_{n,δ} whenever Σy_i≥n+δ; (iii) the paper's own calculation is the support-function evaluation h_K(−ξ)=(1/(n+1))Σy_i and the algebra converting the probability into a halfspace volume, which matches Theorem 2.2 exactly. The event inclusion {S≥ES+δ} ⊆ {K_n(Y)≤1−b_{n,δ}} is one-directional and not an equality, so Theorem 2.1 is not merely the target statement restated. No parameter is fitted to data, no 'prediction' is a renamed fit, and none of the load-bearing citations [VT26], [LY24], [Grü60] overlaps with the present author list. The sole caveat is completeness rather than circularity: Theorem 2.1 is used without proof in this manuscript ('We use the following theorem as an external input [VT26, Theorem 1]'), so the central inequality is contingent on that external result. But an external dependency, even a load-bearing one, is not circular unless the external result reduces to the target or to the authors' own unverified claims; no evidence of that is present. The accompanying Lean formalization is mentioned but is not used as the proof in the paper. Accordingly the circularity score is 0.

Axiom & Free-Parameter Ledger

0 free parameters · 3 axioms · 0 invented entities

No fitted parameters or invented entities. The proof is a reduction to two cited external theorems plus the classical Grünbaum theorem; those theorems are the load-bearing axioms of the derivation.

axioms (3)

domain assumption Vlassis–Thomas theorem (Theorem 2.1): P(K_n(Y)≤α)≤α for independent nonnegative Y with EY_i≤1.
External result [VT26], unproved in this paper, used at α=1-b_{n,δ} in Section 2.2. The main theorem depends on it.
domain assumption Letwin–Yaskin generalized Grünbaum inequality (Theorem 2.2): volume bound for halfspaces cutting a convex body at distance α h_K(-ξ) from the centroid.
External convex-geometry result [LY24], unproved here, used to bound 1-K_n(y) whenever ∑y_i≥n+δ.
domain assumption Grünbaum centroid theorem (α=0 case of Theorem 2.2).
Used for δ=1; classical result [Grü60], also covered by the claimed Lean formalization.

pith-pipeline@v1.3.0-alltime-deepseek · 4528 in / 26273 out tokens · 238584 ms · 2026-07-31T23:22:33.431768+00:00 · methodology

0 comments

read the original abstract

Let $(X_1,\ldots,X_n)$ be independent nonnegative random variables with $\mathbb{E} X_i\le1$, and write $S=\sum_iX_i$. For $\delta>0$, we prove that \[ \mathbb{P}\left(S<\mathbb{E} S+\delta\right)\ge b_{n,\delta}, \] where $b_{n,\delta}=\delta(n/(n+\delta))^n$ for $0<\delta<1$ and $b_{n,\delta}=(1-1/(n+\delta))^n$ for $\delta\ge1$. The bound is sharp for every $n$ and $\delta\ge 1$. In particular, since $b_{n,\delta} \ge e^{-1}$ for $\delta \ge 1$, our result proves Feige's conjecture [Feige, 2004] in the affirmative for $\delta\ge 1$. The proof is found by ChatGPT 5.6 Pro. It combines the exact Dirichlet calibration theorem of Vlassis and Thomas [Vlassis and Thomas, 2026], which resolves Gaffke's conjecture in statistics, with results in convex geometry including Gr\"unbaum's centroid theorem [Gr\"unbaum, 1960] and its generalization by Letwin and Yaskin [Letwin and Yaskin, 2024].

discussion (0)

Forward citations

Cited by 2 Pith papers

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

On the number of factorable induced subgraphs
math.CO 2026-07 accept novelty 8.0

Random induced subgraphs of dense graphs contain F-factors with asymptotically tight probability 1/(rq), where q is the order of a lattice coset group.
From Lecture Notes to Lean: Formalizing a Textbook on Probability Theory
cs.LO 2026-07 conditional novelty 5.0

An ongoing Lean formalization of Shum's probability textbook, using AI-assisted translation and bridge lemmas, has uncovered a textbook error.

Reference graph

Works this paper leans on

22 extracted references · cited by 2 Pith papers

[1]

SIAM Journal on Discrete Mathematics , volume =

Alqasem, Abdulmajeed and Aravinda, Heshan and Marsiglietti, Arnaud and Melbourne, James , title =. SIAM Journal on Discrete Mathematics , volume =. 2024 , doi =

2024
[2]

2009 , eprint =

Dughmi, Shaddin , title =. 2009 , eprint =

2009
[3]

An equivalent conjecture to

D. An equivalent conjecture to. 2025 , eprint =

2025
[4]

A short proof of

Egozcue, Mart. A short proof of. 2025 , eprint =

2025
[5]

, title =

Elton, John H. , title =. 2009 , eprint =

2009
[6]

Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing , pages =

Feige, Uriel , title =. Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing , pages =
[7]

SIAM Journal on Computing , volume =

Feige, Uriel , title =. SIAM Journal on Computing , volume =. 2006 , doi =

2006
[8]

Mathematical Methods of Statistics , volume =

Gaffke, Norbert , title =. Mathematical Methods of Statistics , volume =
[9]

Journal of Combinatorial Theory, Series A , volume =

Garnett, Brian , title =. Journal of Combinatorial Theory, Series A , volume =. 2020 , doi =

2020
[10]

Partitions of mass-distributions and of convex bodies by hyperplanes , journal =

Gr. Partitions of mass-distributions and of convex bodies by hyperplanes , journal =. 1960 , doi =

1960
[11]

2020 , eprint =

Guo, Jiayi and He, Simai and Ling, Zi and Liu, Yicheng , title =. 2020 , eprint =

2020
[12]

Mathematics of Operations Research , volume =

He, Simai and Zhang, Jiawei and Zhang, Shuzhong , title =. Mathematics of Operations Research , volume =. 2010 , doi =

2010
[13]

, title =

Learned-Miller, Erik and Thomas, Philip S. , title =. 2020 , eprint =

2020
[14]

Submodular functions and convexity , booktitle =

Lov. Submodular functions and convexity , booktitle =. 1983 , doi =

1983
[15]

2026 , eprint =

Ming, Jiahao and Ramdas, Aaditya and Shen, Yi and Wang, Ruodu and Waudby-Smith, Ian , title =. 2026 , eprint =

2026
[16]

Geometric Aspects of Functional Analysis , editor =

Oleszkiewicz, Krzysztof , title =. Geometric Aspects of Functional Analysis , editor =. 2012 , doi =

2012
[17]

2017 , eprint =

Paulin, Roland , title =. 2017 , eprint =

2017
[18]

, title =

Samuels, Stephen M. , title =. Annals of Mathematical Statistics , volume =. 1966 , doi =

1966
[19]

, title =

Samuels, Stephen M. , title =
[20]

, title =

Samuels, Stephen M. , title =. Annals of Mathematical Statistics , volume =
[21]

, title =

Vlassis, Nikos and Thomas, Philip S. , title =. 2026 , eprint =

2026
[22]

2024 , eprint =

Letwin, Brayden and Yaskin, Vladyslav , title =. 2024 , eprint =

2024

[1] [1]

SIAM Journal on Discrete Mathematics , volume =

Alqasem, Abdulmajeed and Aravinda, Heshan and Marsiglietti, Arnaud and Melbourne, James , title =. SIAM Journal on Discrete Mathematics , volume =. 2024 , doi =

2024

[2] [2]

2009 , eprint =

Dughmi, Shaddin , title =. 2009 , eprint =

2009

[3] [3]

An equivalent conjecture to

D. An equivalent conjecture to. 2025 , eprint =

2025

[4] [4]

A short proof of

Egozcue, Mart. A short proof of. 2025 , eprint =

2025

[5] [5]

, title =

Elton, John H. , title =. 2009 , eprint =

2009

[6] [6]

Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing , pages =

Feige, Uriel , title =. Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing , pages =

[7] [7]

SIAM Journal on Computing , volume =

Feige, Uriel , title =. SIAM Journal on Computing , volume =. 2006 , doi =

2006

[8] [8]

Mathematical Methods of Statistics , volume =

Gaffke, Norbert , title =. Mathematical Methods of Statistics , volume =

[9] [9]

Journal of Combinatorial Theory, Series A , volume =

Garnett, Brian , title =. Journal of Combinatorial Theory, Series A , volume =. 2020 , doi =

2020

[10] [10]

Partitions of mass-distributions and of convex bodies by hyperplanes , journal =

Gr. Partitions of mass-distributions and of convex bodies by hyperplanes , journal =. 1960 , doi =

1960

[11] [11]

2020 , eprint =

Guo, Jiayi and He, Simai and Ling, Zi and Liu, Yicheng , title =. 2020 , eprint =

2020

[12] [12]

Mathematics of Operations Research , volume =

He, Simai and Zhang, Jiawei and Zhang, Shuzhong , title =. Mathematics of Operations Research , volume =. 2010 , doi =

2010

[13] [13]

, title =

Learned-Miller, Erik and Thomas, Philip S. , title =. 2020 , eprint =

2020

[14] [14]

Submodular functions and convexity , booktitle =

Lov. Submodular functions and convexity , booktitle =. 1983 , doi =

1983

[15] [15]

2026 , eprint =

Ming, Jiahao and Ramdas, Aaditya and Shen, Yi and Wang, Ruodu and Waudby-Smith, Ian , title =. 2026 , eprint =

2026

[16] [16]

Geometric Aspects of Functional Analysis , editor =

Oleszkiewicz, Krzysztof , title =. Geometric Aspects of Functional Analysis , editor =. 2012 , doi =

2012

[17] [17]

2017 , eprint =

Paulin, Roland , title =. 2017 , eprint =

2017

[18] [18]

, title =

Samuels, Stephen M. , title =. Annals of Mathematical Statistics , volume =. 1966 , doi =

1966

[19] [19]

, title =

Samuels, Stephen M. , title =

[20] [20]

, title =

Samuels, Stephen M. , title =. Annals of Mathematical Statistics , volume =

[21] [21]

, title =

Vlassis, Nikos and Thomas, Philip S. , title =. 2026 , eprint =

2026

[22] [22]

2024 , eprint =

Letwin, Brayden and Yaskin, Vladyslav , title =. 2024 , eprint =

2024