$X_1,\cdots,X_n$ such that $P(X_i=1)=P(X_i=-1)=\frac{1}{2}$. Denote $S=\sum_{i=1}^nX_i$. Prove $P(X>\frac{n}{10})<2^{-cn}$ $X_1,\cdots,X_n$ are iid random variables such that $P(X_i=1)=P(X_i=-1)=\frac{1}{2}$.
Denote $X=\sum_{i=1}^nX_i$.
Prove $P(X>\frac{n}{10})<2^{-cn}$ for some $c>0$
I try to use the central limit theorem but I get stuck.
$E[X_i]=0, \sigma=1$
$$P(X>\frac{n}{10})=1-P(X\leq\frac{n}{10})=1-P(\frac{X-\mu n}{\sigma \sqrt{n}}\leq\frac{n-\mu n}{10\sigma\sqrt{n}})=1-P(\frac{X-\mu n}{\sigma \sqrt{n}}\leq\frac{n-\mu n}{10\sigma\sqrt{n}})=1-P(Z\leq\frac{n}{10\sqrt{n}})=1-P(Z\leq\frac{\sqrt{n}}{10})$$
Please help
Thanks !
 A: This is a special case of Bernstein's inequality or Chernoff's bound. But I am not going to use that inequality here.
Consider $e^{tX}=\prod_{i=1}^n e^{tX_i}$. The expectation of which is $\mathbb E(\prod_{i=1}^n e^{tX_i})=(\frac{e^{t}+e^{-t}}{2})^n$ So, by Markov's inequality, the probability of $X\ge n/10$ (or $e^{tX}\ge e^{nt/10}$) is at most  $(\frac{e^{t}+e^{-t}}{2})^n/e^{nt/10}$, or, it is $(\frac{e^{t}+e^{-t}}{2e^{t/10}})^n$.
Take $t=0.1$, we know that $\frac{e^{0.1}+e^{-0.1}}{2e^{0.01}}<0.996$. Thus, $X\ge n/10$ with probability $\le 0.996^n$. Take $c=-\log_2 0.996$ suffice.
A: Here is another approach (It's not an answer to the problem but may be it can help) :
$$\dfrac{X_i + 1}{2}$$
is a Bernoulli distribution of parameter $\dfrac{1}{2}$ then :
$$Y = \sum_{i = 1}^n \dfrac{X_i + 1}{2} = \dfrac{X + n}{2}$$
is a binomial distribution of parameter $\left(n, \dfrac{1}{2}\right)$.
We deduce that :
$$p\left(X > \dfrac{n}{10}\right) = p\left(\dfrac{X + n}{2} > \dfrac{11n}{20}\right) = p \left(Y > \dfrac{11n}{20}\right)$$

*

* By a direct calculi :
$$p\left(X > \dfrac{n}{10}\right) = \dfrac{1}{2^n} \sum_{k = q}^n \binom{n}{k}$$
with $q = \left\lfloor \dfrac{11n}{20} \right\rfloor + 1$.

* By bienayme-chebyshev inequality :
$$p\left(X > \dfrac{n}{10}\right) = p \left(Y - \dfrac{n}{2} > \dfrac{n}{20}\right) \leq p \left(\left|Y - \dfrac{n}{2}\right| > \dfrac{n}{20}\right) \leq \dfrac{100}{n}$$
