Let n ∈ Z_≥ 1, let mu_1 ≥ dotsc ≥ mu_n > 0 satisfy mu_1+dotsm+mu_n=1, and let X_1,dotsc,X_n be independent non-negative random variables with EX_i=1 for every i. Define Z=∑_i=1^n mu_iX_i, and let M=max_1≤ i≤ nmu_i=mu_1, delta>0, and T=1+delta. Feige's conjecture. P(Z<T)≥ min(fracdeltadelta+M,frac1e). Feige proved a weaker version with 1/13 in place of 1/e; the stated constant is sharp in general, but the conjecture itself is presented here as an unproved conjecture.

Feige's lower-tail probability conjecture

The conjecture asserts a sharp lower bound for the lower tail of a weighted sum of independent nonnegative mean-one variables. A 2017 paper shows that Samuels’ conjecture would imply it, but does not prove it.

Known results

Feige proved a universal bound with $1/13$ replacing $1/e$ .
The $1/e$ bound is known for independent log-concave distributions (2022).
Sharpness examples are recorded in the 2017 treatment.

2025–2026 claimed advances

An August 2025 manuscript claims the $1/e$ bound for an unweighted form when $\delta\geq 1$ , while leaving $0<\delta<1$ open. A July 2026 manuscript claims the unweighted case for $0<\delta\leq 1$ ; another claims a different unweighted formulation. These do not establish the weighted statement involving $M$ , and remain unverified.

Current status (as of September 2026): The unrestricted weighted conjecture remains open; only weaker bounds, special cases, and unverified claims for unweighted variants are recorded.

Feige's lower-tail probability conjecture

Primary source

Progress summary

Solutions 0