1

Let $S_n$ denote a binomial $(n,p)$ random variable. The problem is to show that there is a constant $C$ depending only on $p$ such that for all $\epsilon > 0,$ $$P(|S_n/n - p| > \epsilon) \le \frac{C}{n^{10} \epsilon^{20}}.$$ The hint is to use Markov's inequality, but I can't see how it applies... can anyone give another hint or some further advice? Thanks in advance.

Mr. Chip
  • 5,009

1 Answers1

1

You might want to use Chebyshev's inequality, which is a corollary of Markov's inequality (see: http://en.wikipedia.org/wiki/Markov%27s_inequality)

\begin{equation} P( |X - \mathbb{E}X| \geq \varepsilon ) \leq \frac{\text{Var}(X)}{\varepsilon^2} \end{equation} for random variable $X$. It's a special case of Markov's inequality found by considering the function $(X - \mathbb{E}X)^2$. Then you can use the usual rules for $\mathbb{E}[aX]$ and Var$[aX]$ for the random variable $S_n/n$, though I think the denominator in your question might be $n\varepsilon^2$ rather than $n^{10}\varepsilon^{20}$.

Sam Livingstone
  • 246
  • Hi Sam, thanks for your input. I'm familiar with Chebyshev, and I can confirm that my numbers are correct; I really meant 10 and 20, not 1 and 2. – Mr. Chip Apr 14 '14 at 13:29
  • Ah, ok. Well if you use Chebyshev you get $P(|S_n/n - p|> \varepsilon)\leq p(1-p)/n\varepsilon^2$, so maybe that's a starting point at least. I'm not quite sure what the next step is right now though, sorry... – Sam Livingstone Apr 14 '14 at 14:36