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.

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.

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+\delta$ and otherwise equals $0$.
2. $X_1=1+\delta$ with probability $1/(1+\delta)$ and otherwise $X_1=0$. For all $i \ne 1$, $\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.

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.