![](/files/happy5.png)
Sums of independent random variables with unbounded variance
![$ X_1, \dotsc, X_n \geq 0 $](/files/tex/cc1036d1e1d6b5c9517091717d37abff019a4c74.png)
![$ \mathbb{E}[X_i] \leq \mu $](/files/tex/e0268221532981debea25e9446c8ee6f112e1881.png)
![$$\mathrm{Pr} \left( \sum X_i - \mathbb{E} \left[ \sum X_i \right ] < \delta \mu \right) \geq \min \left ( (1 + \delta)^{-1} \delta, e^{-1} \right).$$](/files/tex/03dc1130142ee6fefcc33888e2fb6137211bf327.png)
In comparison to most probabilistic inequalities (like Hoeffding's), Feige's inequality does not deteriorate as goes to infinity, something that is useful for computer scientists.
Let . Feige argued that to prove the conjecture, one only needs to prove it for the case when
and each variable
has the entire probability mass distributed on 0 and
for some
. He proved that
and conjectured that the constant 1/13 may be replaced with
. It was further conjectured that "the worst case" would be one of
- \item one variable has
![$ 1 + \delta $](/files/tex/e08b508dc7682a54f6a17e7e52e8b8f25704dba0.png)
![$ n-1 $](/files/tex/da6174078cbeae6601684c08526200d9254caa11.png)
![$ T $](/files/tex/79f55d2e1d83a7726c807a70cbe756713b0437b6.png)
![$ (1 + \delta)^{-1} \delta $](/files/tex/e0ddf23a272ac0d92389986a0b2ed12a818d3c84.png)
![$ T = n + \delta $](/files/tex/8f017243f8c0f11067852a7b33f0a125ad55edf0.png)
![$ T $](/files/tex/79f55d2e1d83a7726c807a70cbe756713b0437b6.png)
![$ \left(1 - \frac{1}{T}\right)^n \stackrel{n \rightarrow \infty}{\longrightarrow} e^{-1} $](/files/tex/2007fd4bf598f4f36d54bfb885608e4768ae261f.png)
One way to initiate an attack on this problem is to assume and argue that the case when each variable assumes
with probability
and otherwise 0 is indeed the worst.
Bibliography
*[F04] Uriel Feige: On sums of independent random variables with unbounded variance, and estimating the average degree in a graph, STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (2004), pp. 594 - 603. ACM
*[F05] Uriel Feige: On sums of independent random variables with unbounded variance, and estimating the average degree in a graph, Manuscript, 2005, [pdf]
The problem was also referenced at population algorithms, the blog.
* indicates original appearance(s) of problem.