Let $\displaystyle X$ be Binomial $\displaystyle B(p,n)$ with $\displaystyle p>0$ fixed, and $\displaystyle a>0$. How can I show that:
$\displaystyle P(|\frac{X}{n}-p|>a)\le\frac{\sqrt{p(1-p)}}{a^2n}min(\sqrt{p(1-p)},a\sqrt{n})$
To be smaller than the min, means it's smaller than both.
Clearly the first is true by chebyshev's
That means you must also prove that
$\displaystyle P\left( \left| {X\over n}-p\right|>a\right)\le {\sqrt{p(1-p)}\over a\sqrt{n}}$
and that's just the st deviation over a, which is markov.