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
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.