Feige’s conjecture for sums with unbounded variance | Population Algorithms by Petar Maymounkov

Feige’s conjecture for sums with unbounded variance - 2

Under Combinatorial optimization, Computer Science, Mathematics, PR: Probability

I’d like to spell out a conjecture of Feige (which is pretty elegant and simple to state) if for no better reason so that I don’t forget it:

Let $X_1,\dots,X_n$ be independent random non-negative variables with $\E [X_i]=1$ (and arbitrary variance). Then $\Pr[\sum X_i < n + 1] \ge 1/e$ .

The conjecture is a little more general than that, but I’ve purified it for simplicity and, in fact, the above statement is the crux of the conjecture. Feige already proved the conjecture when $1/e$ is replaced by $1/13$ using a, well, horrendous case analysis. So the goal here is really to get the constant $1/e$ and hopefully with a more natural argument.

This conjecture appears in On the sum of nonnegative independent random variables with unbounded variance, Feige’03. I believe that solving implies a better approximation constant for a certain sub-modular optimization problem.

2 Comments ↓

#alex at 2:15 am on April 25th, 2008: Do the random variables have to be nonnegative? Its in the title of the paper, and the conjecture doesn’t sound true without it.
#petar at 8:12 am on April 25th, 2008: Yes, correct, they have to be nonnegative. It may be useful to say that Feige also showed that you can assume wlog that all random variables have support size 2. He further conjeectures that essentially the worst-case setting is when all $X_i$ are identically distributed as $\Pr[X_i=n+1]=(n+1)^{-1}$ and $\Pr[X_i=0]=1-(n+1)^{-1}$ .

Feige’s conjecture for sums with unbounded variance - 2

2 Comments ↓

Desire to speak? ↓