lower-bound for $Pr[X\geq EX]$ Given n random variables, $X_1, ..., X_n$, each takes value 0 or $a_i \in[0, 1]$. $X = \sum_{i=1}^n X_i$ and $EX \geq 1$ is the expected value of $X$. Can we get a lower-bound for $Pr[X \geq EX]$? It seems it can't be too small, may be constant or $\frac{1}{n}$.
 A: This should really be a comment, but it just takes too much space to put in the comment box. I was quite puzzled by Ryan's remark that Feige's problem (with just some constant) is hard while it is a three-liner essentially known to Bernstein. I haven't read Feige's paper, to be honest, so I won't be surprised if it finally turns out that it is exactly what is written there. Still, I decided to post in the hope that someone will clarify what's going on here faster than I find Feige's paper.
Step 1: (trivial reformulation)
Let $Y_k=1-X_k$. Then $Y_k\le 1$ and $EY_k=0$. Put $Y=\sum Y_k$. We need to estimate the probability $P$ that $Y\ge -1$.
Step 2: (Bernstein trick). $Ee^{tY}=\prod_k Ee^{tY_k}$.
Now we have to consider 2 cases.
Case 1: $Ee^Y\le 2$. Then $1\le Ee^{Y/2}\le (1-P)e^{-1/2}+\sqrt{2P}$, and some lower bound for $P$ follows.
Case 2: $Ee^Y>2$. Then we can find $t\in(0,1)$ such that $Ee^{tY}=2$.
Now observe that if $Z\le 1$ is a mean zero random variable, then $Ee^{2Z}\le (Ee^Z)^K$ for some fixed $K$ (the best $K$ in the inequality $F(2z)\le KF(z)$ for the function $F(z)=e^z-1-z$ with $z\in (-\infty,1]$ will certainly work). Applying this observation to each factor in the Bernstein trick, we get $Ee^{2tY}\le 2^K$. Now take $q=2^{-K-1}$, write
$$
\frac 12\le E(e^{tY}-qe^{2tY}-1)
$$
and note that we take an expectation of a function bounded from above by $\frac 1{4q}$ and negative whenever $Y<0$. So, in this case, we even have a bound on $P(Y>0)$.
In response to Lucia's question
It turns out that no new trickery is required here to get some bound depending on $\alpha$ only: the same old argument of Bernstein works perfectly well in this case too.
After centering, we get mean zero random variables $Y_i$ that are $b_i>0$ with probability $\alpha$ and negative otherwise. Now put $Y=\sum Y_i$ and choose $t$ so that $Ee^{tY}=2$. Note that then $\alpha e^{tb_i}\le 2$ for all $i$, so we still are in the bounded from above setting at that moment (with the bound deteriorating as $\alpha\to 0$). Thus, we do exactly the same with $K=\max_{z\le \log\frac 2\alpha}\frac{F(2z)}{F(z)}$ and get some lower bound (small constant times some power of $\alpha$, apparently, which I have no desire to optimize unless somebody really cares about it) on the probability that $Y>0$. 
A: The problem asked (without independence) can be solved. Fix nonnegative real numbers $a_1, …, a_n$.  Define $M = \sum_{i=1}^n a_i$ and assume $M \geq 1$.  Define 
$$\mathcal{X} = \{0, a_1\} \times \{0, a_2\} \times … \times \{0, a_n\} $$
To solve the problem, we first solve a simpler problem (called "Problem 1") below. 

Problem 1: Fix $c \in [1,M]$. We want to find a random vector $(X_1, ..., X_n)$ to solve 
\begin{align}
\mbox{Minimize:} \quad & P\left[\sum_{i=1}^n X_i \geq c\right] \\
\mbox{Subject to:} \quad & E\left[\sum_{i=1}^n X_i\right] = c \\
& (X_1, ..., X_n) \in \mathcal{X}
\end{align}
To solve Probelm 1, define
$$ g_c = \max_{(x_1, ..., x_n) \in \mathcal{X}} \left\{\sum_{i=1}^n x_i : \sum_{i=1}^n x_i < c\right\} $$
That is, $g_c$ is the largest value of $\sum_{i=1}^n x_i$ over all vectors $(x_1, ..., x_n) \in \mathcal{X}$ with components that sum to less than $c$. The max is achievable because $\mathcal{X}$ is a finite set that contains the all-zero vector.  Note that 
$$0 \leq g_c < c \leq M$$ 
Define $\vec{x}_c$ as an element of $\mathcal{X}$ with a sum of components that is equal to $g_c$. Define
$$p_c = \frac{c-g_c}{M-g_c}$$
Observe that $0< p_c \leq 1$. 
Define the random vector
$$ (Z_1, ..., Z_n) = \left\{ \begin{array}{ll}
(a_1, ..., a_n) &\mbox{ with prob $p_c$} \\
\vec{x}_c  & \mbox{ with prob $1-p_c$} 
\end{array}
\right.$$
It is not difficult to show that $E[\sum_{i=1}^nZ_i] = c$ and 
$$P\left[\sum_{i=1}^n Z_i \geq c\right] = p_c $$
Claim
The random vector $(Z_1, ..., Z_n)$ solves problem 1. In particular, the minimum probability is: 
$$ P\left[\sum_{i=1}^n Z_i \geq c\right] = p_c = \frac{c-g_c}{M-g_c}$$
Proof
Define
$$\mathcal{S} = \left\{\sum_{i=1}^n x_i \in \mathbb{R} : (x_1, …, x_n) \in \mathcal{X}\right\}$$
Let $(X_1, ..., X_n)$ be any random vector in $\mathcal{X}$ that satisfies $E[\sum_{i=1}^n X_i]=c$.  Define $S=\sum_{i=1}^n X_i$. Note that: 
$$ S \in \mathcal{S} \subseteq [0, g_c] \cup [c, M]$$
Thus
\begin{align}
c &= E[S|S\geq c]P[S\geq c] + E[S|S\leq g_c](1-P[S\geq c]) \\
&\leq M P[S\geq c] + g_c(1-P[S\geq c]) 
\end{align}
and so 
$$ P[S\geq c] \geq \frac{c-g_c}{M-g_c} = p_c $$
Thus, if $(X_1, ..., X_n)$ is any vector in $\mathcal{X}$ that satisfies the constraints of Problem 1 (namely, $E[\sum_{i=1}^n X_i]=c$), then 
$$ P\left[\sum_{i=1}^n X_i \geq c\right] \geq p_c $$
On the other hand, the lower bound is achieved by the random vector $(Z_1, ..., Z_n)$ defined above. $\Box$

Problem 2: Find a random vector $(X_1, ..., X_n)$ to solve
\begin{align}
\mbox{Minimize:} \quad & P\left[\sum_{i=1}^n X_i \geq E\left[\sum_{i=1}^nX_i\right]\right] \\
\mbox{Subject to:} \quad & E\left[\sum_{i=1}^n X_i\right] \geq 1 \\
& (X_1, ..., X_n) \in \mathcal{X}
\end{align}
Problem 2 can be solved via Problem 1 by optimizing over the mean $c = E[\sum_{i=1}^n X_i]$ over all $c \in [1, M]$.  Thus: 
\begin{align}
p^* &= \inf_{c \in [1, M]} \frac{c-g_c}{M-g_c}
\end{align}
This can be solved by considering two cases:


*

*Case 1: Suppose there is an $x \in \mathcal{S}$ such that $1\leq x < M$.  Then we can choose $c = x + \epsilon$ for some very small value $\epsilon>0$, so that $g_c=x$, and $(c-g_c)/(M-g_c)$ is arbitrarily small.  In this case, $p^*=0$. 

*Case 2: Suppose there is no $x \in \mathcal{S}$ such that $1\leq x < M$. So $g_c=g_1$ for all $c \in [1,M]$. So we choose $c=1$ and 
$$ p^* = \frac{1-g_1}{M-g_1}$$
