← All problems

Feige’s 1/e1/e conjecture

22 years old · traced to

Conjecture 1 (Feige). Let X1,…,XnX_1,\ldots,X_n be arbitrary nonnegative independent random variables with expectations μ1,…,μn\mu_1,\ldots,\mu_n, where μi≤1\mu_i\leq 1 for every ii, and let X=∑i=1nXiX=\sum_{i=1}^n X_i and μ=∑i=1nμi\mu=\sum_{i=1}^n\mu_i. For every δ>0\delta>0 and every positive integer nn, one of the following two examples is the worst case for P(X<μ+δ)\mathbb{P}(X<\mu+\delta): (i) X1=1+δX_1=1+\delta with probability 1/(1+δ)1/(1+\delta) and X1=0X_1=0 otherwise, while X2,…,XnX_2,\ldots,X_n are identically equal to 11; or (ii) each XiX_i equals n+δn+\delta with probability 1/(n+δ)1/(n+\delta) and equals 00 otherwise. In particular, at δ=1\delta=1, the conjecture asserts that for every finite sum of independent nonnegative random variables with EXi≤1\mathbb{E}X_i\leq 1, P(∑i=1nXi<E(∑i=1nXi)+1)≥1/e\mathbb{P}(\sum_{i=1}^nX_i<\mathbb{E}(\sum_{i=1}^nX_i)+1)\geq 1/e.

References

Progress summary

Refreshed
Open · solution reported

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 1/e1/e of lying below its mean plus 11, and proposes two extremal examples for the more general threshold δ\delta.

Known results

  • Feige’s original bound was 1/131/13.
  • He, Zhang, and Zhang improved it to 1/81/8; Garnett to 7/507/50.
  • Guo, He, Ling, and Liu obtained approximately 0.17980.1798.
  • The 1/e1/e bound was known for discrete log-concave and identically distributed variables.

July–August 2026 claimed proofs

A July preprint claims the δ\delta =1=1 case with the sharp finite-dimensional bound (n/(n+1))n≥1/e\left(n/(n+1)\right)^n\geq 1/e, while an August preprint reports a sharp formula under an equal-means reduction. An August 2025 preprint separately claims the full bound P(X<μ+δ)≥min⁡{δ/(1+δ),e−1}\mathbb{P}(X<\mu+\delta)\geq\min\{\delta/(1+\delta),e^{-1}\}, but does not explicitly prove the problem’s stronger two-example extremal assertion. These claims are unverified.

Current status (as of August 2026): The 1/e1/e inequality has multiple claimed proofs, including claims covering the general δ\delta bound, but none is independently verified, and the stated two-example extremal conjecture remains open.

Sources

Solutions 0

No solutions have been posted yet.