The relative error of approximating a binomial Are there any good approximations for a binomial CDF that work well in terms of the relative error, as opposed to absolute?  For the usual normal approximation, the absolute error is very well-studied and does an excellent job, but obviously the relative error could be arbitrarily bad by comparing CDF's at $X=0$ since the normal distribution will always give a positive (albeit small) value.  Has anyone proposed an approximation whose relative error is known to behave well?
 A: $\newcommand\ep\varepsilon$Let $S_n$ be a random variable (r.v.) with the binomial distribution with parameters $n,p$. Then, by Theorems 1 and 2,
$$P(S_n\ge an)\sim\frac1{1-r}\frac1{\sqrt{2\pi(1-a)a}}e^{-n D(a\|p)}$$
where $n\to\infty$, $1>a>p>0$, $an$ is an integer,
$$r:=\frac p{1-p}\Big/\frac a{1-a},$$
$$D(a\|p):=a\ln\frac ap+(1-a)\ln\frac{1-a}{1-p},$$
and
$$\frac{(a-p)^2}{(1-p)^2}\frac{1-a}{a}\,n\to\infty. \tag{1}\label{1}$$
In particular, condition \eqref{1} will hold if $p\in(0,1)$ is fixed and $(1-a)n\to\infty$ and $(a-p)^2 n\to\infty$.
If $n\to\infty$, $1>a>p>0$, $k:=an$ is an integer, $(1-a)n=O(1)$, and $p$ is fixed (or, more generally, $(1-a)p/(1-p)\to0$), then it is easy to see that
$$P(S_n\ge an)=P(S_n\ge k)\sim P(S_n=k)=\binom nk p^k(1-p)^{n-k}
\sim\frac{(np)^k}{k!}\,(1-p)^{n-k}.$$
If $p\in(0,1)$ is fixed and $n\to\infty$ and $(a-p)^2 n=O(1)$, then, by the central limit theorem,
$$P(S_n\ge an)\sim P\Big(Z\ge(a-p)\sqrt{\frac n{p(1-p)}}\,\Big),$$
where $Z\sim N(0,1)$.
The three cases considered above provide a complete description of the asymptotic behavior of the right-tail probabilities $P(S_n\ge an)$ at least when $p\in(0,1)$ is fixed -- in fact, the same will hold if $p$ just stays away from $0$ and from $1$. (If $p$ is close to $0$ or $1$, then a Poisson approximation becomes relevant.)
Clearly, the similar results hold for the left-tail probabilities $P(S_n\le an)$, with $1>p>a>0$.
A: Don't forget that far out in the left tail, the Binomial CDF is multiplicatively approximated by the PMF, because terms grow geometrically.
Example. For $t \leq \frac{np}{2}$, we claim $\Pr[X = t] \leq \Pr[X \leq t] \leq 2\Pr[X = t]$.
Proof.
Let $f = \Pr[X = t] = {n \choose t} p^t (1-p)^{n-t}$.
Immediately, $\Pr[X \leq t] \geq f$.
On the other side:
\begin{align}
\Pr[ X \leq t ]
&= \sum_{k=t}^0 {n \choose k} p^k (1-p)^{n-k}  \\
&= f ~+~ f \frac{1-p}{p} \frac{t}{n-t+1} ~+~ f \left(\frac{1-p}{p}\right)^2 \frac{t(t-1)}{(n-t+1)(n-t+2)} ~+~ \cdots \\
&\leq f \sum_{j=0}^t \left(\frac{(1-p)t}{p(n-t+1)}\right)^j \\
&\leq f \frac{1}{1 - (1-p)t/(p(n-t+1))}  \\
&\leq f \frac{1}{1 - (1/2)}  \\
&=    2f.
\end{align}
At the end, we used $t \leq \frac{np}{2}$ as follows:
\begin{align}
\frac{(1-p)t}{p(n-t+1)}
&\leq \frac{t - pt}{np - pt}  \\
&=    \frac{1 - p}{(np/t) - p}  \\
&\leq \frac{1 - p}{2 - p}  \\
&\leq \frac{1}{2} .
\end{align}
A: My paper here (Adv. Appl. Prob., 21 (1989) 475-478), Theorem 2, provides an estimate over all values of the parameters with relative error that is $o(1)$ if either $\sigma\to\infty$ or $x\sigma\to\infty$, where $\sigma$ is the standard deviation and $x$ is the number of standard deviations from the mean.
