$S_n = \sum\limits_{i=1}^{n} X_i$ where $X_i$'s are i.i.d RVs. $\mathbb{P}(X_i = 1) = p, \mathbb{P}(X_i = 0) = 1-p$. Prove that for any $\epsilon > 0$, $\mathbb{P} \left(\frac{S_n}{n} > p+\epsilon\right) \leq e^{\frac{1}{4}n\epsilon^2}$.
My proof is:
$\mathbb{E}(X_i) = p$, Var$(X)=p(1-p)$, both $< + \infty$.
By WLLN, $\forall \epsilon > 0$,$\mathbb{P} \left(\left|\frac{S_n}{n} - p\right| > \epsilon\right) \rightarrow 0$ as $n \rightarrow + \infty$.
Then $\mathbb{P} \left(\frac{S_n}{n}> p+\epsilon\right)\rightarrow 0$.
Since $e^{\frac{1}{4}n\epsilon^2} \geq 0$, $\mathbb{P} \left(\frac{S_n}{n} > p+\epsilon\right) \leq e^{-\frac{1}{4}n\epsilon^2}$.
Am I right? Thank you so much!
We know that $$S_n \sim B(n,p)$$
Then: \begin{align*} \mathbb{P}(\frac{S_n}{n} \geq p + \epsilon) & \leq \sum_{k \geq n(p+\epsilon)} \binom{n}{k} p^k q^{n-k} \\ \leq & \sum_{k \geq n(p+\epsilon)} e^{-\lambda((p+\epsilon)n - k)} \binom{n}{k} p^k q^{n-k} \\ \leq & e^{-\lambda n \epsilon} \sum_{k=0}^n \binom{n}{k} (pe^{\lambda q})^k (qe^{-\lambda p})^{n-k} = \\ = & e^{-\lambda n \epsilon} (p e^{\lambda q} + q e^{-\lambda p})^n \leq \\ \leq & e^{-\lambda n \epsilon} ( pe^{\lambda^2 q^2} + q e^{\lambda^2 p^2})^n \leq \\ \leq & e^{-\lambda n \epsilon} e^{\frac{1}{8} \lambda^2 n} \end{align*}
note that $(p+\epsilon)n - k < 0$, so first $\exp(\cdot)$ is always greater than one, therefore first inequality is true.
Second one: $e^{\lambda p(n-k) + \lambda k} = e^{-\lambda pn + \lambda pk - \lambda pk + \lambda k} = e^{-\lambda p(n-k)} e^{\lambda k (1-p)} = (e^{-\lambda q})^k (e^{-\lambda p})^{n-k}$. We use $a^k b^k = (ab)^k$ and then just add terms up to $k=0$. Everything is nonnegative, so we still have inequality
In second to last we use $e^x \leq x + e^{x^2}$ and $pe^{qx} + qe^{-px} \leq e^{\frac{1}{8} x^2}$
Now we pick $\lambda$ such that RHS is minimized, $\lambda = 4 \epsilon$