How to estimate this probability of sum of $(-1,+1)$ valued random variables? Let $x_1,\ldots,x_n$ be independent random variables and $\mathbb{P}(x_i=\pm1)=1/2.$
Prove that exists $C>0$ such that for $0\leq\Delta \leq n/C$,
$$
\mathbb{P}\big(\sum_{i=1}^n x_i>\Delta\big)\geq\frac{1}{C}\exp(-\frac{\Delta^2}{Cn})
$$
The Chernoff bound is an upper bound of the probability, while what I want to prove is lower bound.  Is the statement correct? Is there a reference about the lower bound estimate?
 A: Fix $0<\epsilon<\delta<\frac{1}{2}$, and let $\Delta \in [0, (1-2\delta) n]$. Then
\begin{align*}
P := \mathbb{P}\bigg(\sum_{i=1}^n x_i>\Delta\bigg)
&= \mathbb{P}\bigg(\sum_{i=1}^n \frac{1-x_i}{2} < \frac{n-\Delta}{2} \bigg) \\
&= \sum_{k < \frac{n-\Delta}{2}} \binom{n}{k} \frac{1}{2^n} \\
&\geq \sum_{\epsilon n \leq k < \frac{n-\Delta}{2}} \binom{n}{k} \frac{1}{2^n} \\
&\geq c_1 \sum_{\epsilon n \leq k < \frac{n-\Delta}{2}} \frac{n^{n+\frac{1}{2}}}{k^{k+\frac{1}{2}}(n-k)^{n-k+\frac{1}{2}}} \frac{1}{2^n},
\end{align*}
for $c_1 = \sqrt{2\pi}/e^2$, where the last line follows from the quantitative form of the Stirling's approximation Now by writing $p = k/n \in [\delta, \frac{1}{2}]$, we have
$$ \frac{n^{n+\frac{1}{2}}}{k^{k+\frac{1}{2}}(n-k)^{n-k+\frac{1}{2}}}
= \frac{2^{H(p)n}}{\sqrt{np(1-p)}}, $$
where $H(p)$ is the binary entropy to the base $2$. Noting that $H(p) \geq 1-c_2(p-\frac{1}{2})^2$ holds on $p \in [\delta, \frac{1}{2}]$ for some constant $c_2 > 0$ depending only on $\delta$, we get
\begin{align*}
P
&\geq \frac{c_3}{\sqrt{n}} \sum_{\epsilon n \leq k < \frac{n-\Delta}{2}} 2^{-c_2 n(p-\frac{1}{2})^2}
\end{align*}
where $c_3 = c_1/\sqrt{\delta(1-\delta)}$. Approximating this sum by the integral, we get
\begin{align*}
P
&\geq \frac{c_3}{\sqrt{n}} \int_{\epsilon n+1}^{\frac{n-\Delta}{2}-1} 2^{-c_2 n(\frac{x}{n}-\frac{1}{2})^2} \, \mathrm{d}x \\
&= c_3 \int_{\frac{\Delta}{2\sqrt{n}}+\frac{1}{\sqrt{n}}}^{(\frac{1}{2}-\epsilon)\sqrt{n}-\frac{1}{\sqrt{n}}} 2^{-c_2 u^2} \, \mathrm{d}u \tag{$\textstyle u=\frac{\sqrt{n}}{2}-\frac{x}{\sqrt{n}}$}
\end{align*}
Using this lower bound and noting that $\frac{\Delta}{2\sqrt{n}} \leq (\frac{1}{2}-\delta)\sqrt{n} < (\frac{1}{2}-\epsilon)\sqrt{n}$, it can be shown that there exist $c_4, c_5 > 0$, depending only on $\delta$ and $\epsilon$, such that
$$ P \geq c_4 e^{-c_5 \frac{\Delta^2}{n}} $$
uniformly in $\Delta \in [0, (1-2\delta)n]$.
