A version of the non-adaptive problem was studied by Uriel Feige, using slightly different language. In [his paper][1], "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][2]. 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. [1]: http://www.wisdom.weizmann.ac.il/~feige/Others/newmarkov.pdf [2]: http://www1.se.cuhk.edu.hk/~zhang/Reports/seem2007-09-rev.pdf