TOPICS
Search

Feige's Conjecture

Feige's conjecture (Feige 2006) is the probability inequality asserting that, for independent nonnegative random variables X_1, ..., X_n with expectation values at most 1, their sum S=X_1+...+X_n satisfies

P(S<E[S]+1)>=1/e.

Here e is the base of the natural logarithm. The constant 1/e is best possible uniformly in n.

Fu et al. (2026) proved the sharper finite-n bound

P(S<E[S]+1)>=(n/(n+1))^n.

Equality holds when the random variables are independent, each taking the value n+1 with probability 1/(n+1) and 0 otherwise. Then E[S]=n, and S<n+1 occurs precisely when all the random variables vanish.

Fu et al. (2026) credit ChatGPT 5.6 Pro with finding their proof. Nie and Wei (2026) gave a separate proof with AI assistance, and a Lean formalization of the sharp bound is available from Zhang (2026).

See also

Expectation Value, Probability Inequality, Random Variable

Explore with Wolfram|Alpha

References

Feige, U. "On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph." SIAM J. Comput. 35, 964-984, 2006. https://doi.org/10.1137/S0097539704447304.Fu, W.; Han, Y.; Wang, G.; Yan, J.; Zhang, P.; and Zhou, Z. "Sharp Small-Deviation Inequalities for Sums of Independent Nonnegative Random Variables." 27 Jul 2026. https://arxiv.org/abs/2607.23980.Nie, Z. and Wei, J. "On Feige's Conjecture." 27 Jul 2026. https://arxiv.org/abs/2607.24528.Zhang, P. "Feige." 2026. https://github.com/pengzhang91/Feige.

Cite this as:

Weisstein, Eric W. "Feige's Conjecture." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/FeigesConjecture.html

Subject classifications