Feige’s conjecture
Conjecture 1 (Feige). Let be arbitrary nonnegative independent random variables with expectations , where for every , and let and . For every and every positive integer , one of the following two examples is the worst case for : (i) with probability and otherwise, while are identically equal to ; or (ii) each equals with probability and equals otherwise. In particular, at , the conjecture asserts that for every finite sum of independent nonnegative random variables with , .
Progress summary
A proof has been claimed for the probability bound, but no independent confirmation has established it, and the stronger worst-case description remains unsettled.
Feige’s conjecture asks whether every such sum has probability at least of lying below its mean plus , and proposes two extremal examples for the more general threshold .
Known results
- Feige’s original bound was .
- He, Zhang, and Zhang improved it to ; Garnett to .
- Guo, He, Ling, and Liu obtained approximately .
- The bound was known for discrete log-concave and identically distributed variables.
July–August 2026 claimed proofs
A July preprint claims the case with the sharp finite-dimensional bound , while an August preprint reports a sharp formula under an equal-means reduction. An August 2025 preprint separately claims the full bound , but does not explicitly prove the problem’s stronger two-example extremal assertion. These claims are unverified.
Current status (as of August 2026): The inequality has multiple claimed proofs, including claims covering the general bound, but none is independently verified, and the stated two-example extremal conjecture remains open.
Solutions 0
No solutions have been posted yet.