Show probability bound. Let $Y$ be the number of successes in $n$ trials of a Bernoulli experiment with success probability $p$.  Show that:
$$ Pr(|\frac{Y}{n} - p |<e) \geq 1 - \frac{1}{4ne^2}$$
I tried starting with Chebychev and work backwards but I got stuck:
I used $np(1-p)$ for variance since binomial.
$$
\begin{align}
Pr(|Y-\mu|\geq a) &\leq \frac{np(1-p)}{a^2}\tag1\\
Pr(|\frac{Y}{n}-\frac{\mu}{n}|\geq \frac{a}{n}) &\leq \frac{np(1-p)}{a^2}\tag2\\
\end{align}
$$
Since for binomial $\mu/n=p$
$$
\begin{align}
Pr(|\frac{Y}{n}-p|\geq \frac{a}{n}) &\leq \frac{np(1-p)}{a^2}\tag3\\
1-Pr(|\frac{Y}{n}-p|\geq \frac{a}{n}) &\geq 1-\frac{np(1-p)}{a^2}\tag4\\
Pr(|\frac{Y}{n}-p|< \frac{a}{n}) &\geq 1-\frac{np(1-p)}{a^2}\tag5\\
\end{align}
$$
I then set $e=a/n$
$$
\begin{align}
Pr(|\frac{Y}{n}-p|< e) &\geq 1-\frac{np(1-p)}{(en)^2}\tag6\\
Pr(|\frac{Y}{n}-p|< e) &\geq 1-\frac{p(1-p)}{e^2n}\tag7\\
Pr(|\frac{Y}{n}-p|< e) &\geq \frac{e^2n-p(1-p)}{e^2n}\tag8\\
\end{align}
$$
I gave up here because I still need to flip the greater than in the prob and get the RHS to be exactly the same (how??) and I still don't really know if this is the right approach to start with anyway.
 A: Check out Hoeffding's inequality on Wikipedia. It won't give you exactly the answer that you're looking for: instead, it will give you a far stronger one (asymptotically, as $n$ gets large)! Regarding the precise formlation that you have, you're almost there: all you need to do is note that
$$ p(1-p) \le \tfrac14 \quad \text{for all} \quad p \in [0,1]. $$
I'd definitely advise looking at the Wiki page though. There you'll find a proof of a slightly more general result -- it generalised from Binomial, ie sum of independent Bernoullis, to a sum of independent bounded random variables.
I leave the proof to your reading of that page, and just look here at how to apply it. It says that
$$ P( |Bin(n,p) - np| \ge \epsilon n ) \le 2 \exp(-2 \epsilon^2 n). $$
Note that, $|Y/n - p| < e$ if and only if $|Y - pn| < en$. Hence, applying this, we find that
$$ P( |Y/n - p| \ge e ) = P( |Y - pn| \ge en ) \le 2 \exp(- 2 e^2 n). $$
Taking the compliment gives the probability you desire.
This actually shows a much better bound that you've been asked to show for large $n$. Note that Hoeffding is valid for all $n$.
A: By the AM-GM inequality, $$\sqrt{p(1-p)} \le \frac{p+(1-p)}{2} = \frac12.$$
Therefore, $$p(1-p) \le \frac14.$$
\begin{align}
Pr(|\frac{Y}{n}-p| < e) &\geq 1-\frac{np(1-p)}{(en)^2}\\
&= 1-\frac{p(1-p)}{e^2n}\\
&\ge 1-\frac{1}{4e^2n}\\
\end{align}
