2 of 3
Fixed minor mistake
Woett
• 1.5k
• 14
• 23

A version of the non-adaptive problem was studied by Uriel Feige, using slightly different language. In his paper, "On Sums of Independent Random Variables with Unbounded Variance, and Estimating the Average Degree in a Graph", he proves the following theorem.

Let $$X_1,\ldots,X_n$$ be non-negative independent random variables with expectations $$\mu_1,\ldots,\mu_n$$, respectively, with all $$\mu_i \le 1$$. Let $$X=\sum_{i=1}^n X_i$$ and $$\mu=\sum_{i=1}^n \mu_i=\mathbb{E}X$$. Then for all $$\delta > 0$$,

$$\mathbb{P}[ X < \mu + \delta] \ge \min(\delta/(1+\delta),1/13).$$

The value $$1/13$$ was later improved to $$1/8$$ by He, Zhang and Zhang. Feige conjectures that in the setting of the above theorem, for every $$n$$, for all $$\delta > 0$$ one of the following two examples minimizes $$\mathbb{P}[ X < \mu + \delta]$$.

1. For each $$1 \le i \le n$$, $$X_i=n+\delta$$ with probability $$1/(n+\delta)$$ and otherwise equals $$0$$.
2. $$X_1=1+\delta$$ with probability $$1/(1+\delta)$$ and otherwise $$X_1=0$$. For all $$1 < i \le n$$, $$\mathbb{P}[X_i=1]=1$$.

If Feige's conjecture is correct, the term $$1/13$$ may in fact be replaced by $$1/e$$. The first step in Feige's argument is to show that the general question may be reduced to the case of random variables whose support contains at most one non-zero value; this makes the problem look rather similar to the one given above.