Let $p\in (0,1)$ be fixed and let $X$ be a binomial random variable with parameters n and p. Consider a related normal random variable $N$ with mean $np$ and variance $np(1-p)$. Is it true that for some $x=x(n)$ we have $P(X>np+x)=(1+o(1))P(N>np+x)$? That is, if true, I would like to know how large $x$ can be. Is it true that the natural borderline is $x=O(\sqrt{n})$?



Large deviations for bernoulli sums
There are quite a lot of approximations more accurate than the pure normal distribution, with a large literature difficult to sort out. You can see several in [this paper](http://cs.anu.edu.au/~bdm/papers/littlewood2.pdf) (Adv. Appl. Prob., 21 (1989) 475-478). If I am expanding Theorem 1 correctly, for fixed $p$ that is away from $\frac 12$, the relative error is $o(1)$ iff $x=o(n^{2/3})$. For $p=\frac12$, the symmetry makes the leading error term vanish so the error is still $o(1)$ further out, maybe for $x=o(n^{4/5})$.


All of this is for $x>0$. For $x<0$ the accuracy is fine all the way to the end since it approaches 1.


