Sharp Tail Bounds Beyond Twice The Mean

Let $X_1,\dots ,X_n$ be independent nonnegative random variables with $\text{𝔼}[X_i]\le 1$. We prove that, for every $t\ge 2n+1$,

To prove this, we consider a relaxed optimization problem over a set of sequences of ordered, but non-independent random variables. This allows us to reformulate it recursively as a dynamic programming problem. The bound becomes an equality for the binary i.i.d. random variables satisfying $\text{ℙ}[X_i=0]=1-1/t$ and $\text{ℙ}[X_i=t]=1/t$, which remains a maximizer in the relaxed problem.