Feige’s small-deviation probability conjecture

For independent nonnegative random variables Xᵢ with E[Xᵢ]≤1, how small can P(ΣXᵢ<E[ΣXᵢ]+δ) be? Feige’s unit-slack conjecture asks for the universal lower bound e⁻¹ at δ=1; finite-n and other positive-slack bounds refine it.

Why it matters and what counts as progress

Why it matters: A sharp finite-n small-deviation bound strengthens Feige’s universal unit-slack prediction and determines its finite-size dependence.

What counts as progress: Prove the unit-slack bound or a sharp finite-n formula, such as (1−1/(n+δ))ⁿ for δ≥1.

How the problem developed

2006 · Conjecture [1]
Uriel Feige Conjectured a universal lower bound 1/e for the probability that a sum of independent nonnegative random variables is below its mean plus one, under individual mean bounds of one.
27 Jul 2026 · Partial resolution [2]
Weibo Fu, Yanjun Han, Guanyang Wang, Jun Yan, Peng Zhang and Zhengqing Zhou Proved a sharp finite-n small-deviation bound and thereby established Feige’s conjectured 1/e lower bound for deviations δ ≥ 1.

AI contribution

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

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

For independent nonnegative random variables X₁,…,Xₙ with E[Xᵢ]≤1 and S=ΣXᵢ, Fu, Han, Wang, Yan, Zhang and Zhou prove P(S<E[S]+δ)≥δ(n/(n+δ))ⁿ for 0<δ<1, and ≥(1−1/(n+δ))ⁿ for δ≥1. The second finite-n bound is sharp and implies Feige’s unit-slack e⁻¹ conjecture.

AI involvementAI-led

ImportanceMajor

Technical verificationFormal (human)

Human understandingFull