On Samuels' Conjecture

Abstract

Let $0\le {\mu }_1\le \cdots \le {\mu }_n$ and let $\lambda >{\sum }_{i=1}^n{\mu }_i$. Let $X_1,...,X_n$ be independent nonnegative random variables satisfying $\mathbb{E}{X}_i={\mu }_i$, and write $D_i:=\lambda -{\sum }_{k=1}^{i-1}{\mu }_k$ for $1\le i\le n$. We prove that $$\underset{X_1,...,X_n}{\inf }\mathbb{P}\left(\sum _{i=1}^n{X}_i<\lambda \right)=\underset{1\le i\le n}{\min }\prod _{j=i}^n\left(1-\frac{{\mu }_j}{D_i}\right).$$ The bound is sharp and is attained. This proves Samuels' conjecture. Feige's conjecture is thereby resolved, since it follows immediately from the equal-means case. The proof is self-contained.