

























A well-known discovery of Feige's is the following: Let $X_1, \ldots, X_n$ be nonnegative independent random variables, with $\mathbb{E}[X_i] \leq 1 \;\forall i$, and let $X = \sum_{i=1}^n X_i$. Then for any $n$, \[\Pr[X < \mathbb{E}[X] + 1] \geq α> 0,\] for some $α\geq 1/13$. This bound was later improved to $1/8$ by He, Zhang, and Zhang. By a finer consideration of the first four moments, we further improve the bound to approximately $.14$. The conjectured true bound is $1/e \simeq .368$, so there is still (possibly) quite a gap left to fill.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。