Lower bound on probability of sum of random variables Suppose that the random variables $X_i, i = 1,2,\ldots,n$ are i.i.d.  Suppose $0 \leq X_i \leq 4n^2$ with probability 1 for all $i$.  Suppose that $\mathbb{E}(X_i) \geq n$ for all $i$.  Show that $$\mathbb{P}(X_1 + X_2 + \cdots + X_n \geq n^2/2) \geq \frac{1}{20}.$$
Hint:  Is there a lower bound inequality that you might try here?  What do you need to compute?  How can you use the hypotheses?

I tried something that seemed like it was working at first, but didn't get me anywhere.  Here's what I did, considering only the case where $n$ is even:
Define $S := X_1 + X_2 + \cdots + X_n$.  Then $\mathbb{E}(S) \geq n^2$.  We have \begin{align*}
n^2 \leq \mathbb{E}(S) &\leq  \mathbb{P}(0 \leq S) + \mathbb{P}(1 \leq S) + \cdots + \mathbb{P}(4n^3 - 1 \leq S)\\
&= \left(\mathbb{P}(0 \leq S) + \cdots + \mathbb{P}(n^2/2 - 1 \leq  S) \right) \\
&\qquad {}+ \left(\mathbb{P}(n^2/2 \leq S) + \cdots + \mathbb{P}(4n^3 - 1 \leq S)  \right) \\
&= n^2 + (4n^3 - n^2/2)\mathbb{P}(n^2/2 \leq S) 
\end{align*}
This yields $$\frac{1}{8n-1} \leq \mathbb{P}(n^2/2 \leq S)$$
Which is a pretty nice result, but isn't what the problem asks for.  Any help would be greatly appreciated.
 A: I am at a loss for an inequality that ends up being free of $n$. However, in my attempts I came up with what appears to be a counterexample to what you are trying to prove.

Assuming that $0\leq X_i\leq 4n^2$ is not a typo:
Let $\mu_n=E[S],p_n:=P(S\geq n^2/2), \;U:=E[S|S\geq n^2/2,\mu_n>n^2],\; L:=E[S|S<n^2/2,\mu_n>n^2]$
We know that: $E[S_n]=pU+(1-p)L\geq n^2$ for any distribution by simple linearity of expectation.
This implies:
$p_n\geq\frac{n^2-L}{U-L}:U\in[n^2,4n^3],L\in[0,n^2/2)$
If we try to minimize wrt $U,L$, the lower bound on $p_n$ is achieved when $U=4n^3,L\to n^2/2$
Thus (forcing $E[S]=n^2$, $U=4n^3$ and letting $L\to n^2/2$):
$p_n\to\frac{n^2}{8n^3-n^2}\xrightarrow{n\uparrow}0 \implies \exists(c,L,U):p_n<\frac{1}{20}\forall n>c$
Note that the above solution is consistent with the hypotheses of the theorem:
$H_1:E[X_i]=n\geq n$ 
$H_2:X_i \in [0,4n^2]$
...yet we've arrived at a solution that violates the theorem. It appears something is amiss with either the assumptions and/or the theorem.
In particular, it seems that $E[S]\geq n^2$ is not a strong enough constraint to ensure that the lowest possible probability is $\frac{1}{20}$.
Now, if $E[X_i]\geq n^2$, then you have something, since $E[S] \to 1/8 > 1/20$
