Upper bound on the average of independent Rademacher random variables Given a sequence of Rademacher random variables $\{X_k\}_{k\geq1}$. The definition of Rademacher random variables can be found in Inequality with Rademacher variables.
I was wondering how to prove that $\mathbb{P}\left(\frac{\sum X_i}{n}\geq x\right) \leq \exp(-nF(x))$ where $$F(x)=\frac{1}{2}(1-x)\ln(1-x)+\frac{1}{2}(1+x)\ln(1+x)\,.$$
My problem is I don't even know which way I should follow to prove it. The Hoeffding inequality looks useful. But I cannot find a starting point 
 A: This is very similar to the standard derivation of the Chernoff bound, with some nice simplifications coming from the knowledge that the summands are Rademacher.

Fix $x\in(0,1)$. Start like the proof of the Chernoff bound, using Markov's inequality:
$$
\mathbb{P}\left\{ \sum_{k=1}^n X_k \geq nx \right\} = \mathbb{P}\left\{ e^{t\sum_{k=1}^n X_k} \geq e^{tnx} \right\} \leq \frac{\mathbb{E}[e^{t\sum_{k=1}^n X_k}]}{e^{tnx}} \tag{1}
$$
for every $t> 0$.
By independence of the $X_k$'s, we can thus write, for all $t>0$,
$$
\mathbb{P}\left\{\frac{1}{n}\sum_{k=1}^n X_k \geq x \right\} \leq \frac{\mathbb{E}[\prod_{k=1}^n e^{t X_k}]}{e^{tnx}} 
=\frac{\prod_{k=1}^n\mathbb{E}[e^{t X_k}]}{e^{tnx}} 
=\frac{\cosh^n t}{e^{tnx}} = \left(\frac{\cosh t}{e^{tx}}\right)^n  \tag{2}
$$
the second-to-last equality using the expression of the MGF of a Rademacher r.v.. It only remains to choose $t>0$ to minimize the RHS. Studying the function $t\mapsto \frac{\cosh t}{e^{tx}}$ by differentiation shows that this minimum is achieved for
$$
t^\ast \stackrel{\rm def}{=} \frac{1}{2}\ln\frac{1+x}{1-x}\,.\tag{3}
$$
Plugging back into (2), this yields
$$
\mathbb{P}\left\{\frac{1}{n}\sum_{k=1}^n X_k \geq x \right\} \leq \left(\frac{\cosh t^\ast}{e^{t^\ast x}}\right)^n = e^{-n F(x)} \tag{4}
$$
where
$$\begin{align*}
F(x) &= \ln \frac{e^{t^\ast x}}{\cosh t^\ast}
= \ln\left( \sqrt{1-x^2}\cdot e^{t^\ast x} \right)
= \ln\left( \sqrt{1-x^2}\cdot e^{\frac{x}{2}\ln\frac{1+x}{1-x}} \right)\\
&= \frac{1}{2}\ln\left( (1+x)(1-x)\cdot e^{x\ln\frac{1+x}{1-x}} \right)
= \frac{1}{2}\ln\left( (1+x) e^{x\ln(1+x)}\cdot (1-x)e^{-x\ln(1-x)} \right)\\
&= \frac{1}{2}\left( \ln(1+x) + x\ln(1+x) + \ln(1-x)-x\ln(1-x)\right) \\
&= \frac{1}{2}\left( (1+x)\ln(1+x)+(1-x)\ln(1-x)\right) \tag{5}
\end{align*}$$
as sought.
