lower bound for being far away from the mean

Question

Let $S = \sum^n _{i=1} S_i$ be a sum of n independent random variables, each attaining values $+1$ and $−1$ with equal probability. Let $P(n,Δ) = Pr [S > Δ]$.

Prove that for $Δ ≤ n/C$, $P(n,Δ) ≥ \frac{1}{C} exp(\frac {-Δ^2}{Cn}) $ , where C is a suitable constant.

i really don't know how to approach this problem.

is there any hint?

thanks

Answer 1

You can directly apply the special case of Chernoff bounds to this problem. A loose upper bound can be derieved from Chebyshev's inequality as well.