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 wellstudied 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?
3 Answers
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 (1p)^{nt}$. 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 (1p)^{nk} \\ &= f ~+~ f \frac{1p}{p} \frac{t}{nt+1} ~+~ f \left(\frac{1p}{p}\right)^2 \frac{t(t1)}{(nt+1)(nt+2)} ~+~ \cdots \\ &\leq f \sum_{j=0}^t \left(\frac{(1p)t}{p(nt+1)}\right)^j \\ &\leq f \frac{1}{1  (1p)t/(p(nt+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{(1p)t}{p(nt+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}
$\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{1r}\frac1{\sqrt{2\pi(1a)a}}e^{n D(a\p)}$$
where $n\to\infty$, $1>a>p>0$, $an$ is an integer,
$$r:=\frac p{1p}\Big/\frac a{1a},$$
$$D(a\p):=a\ln\frac ap+(1a)\ln\frac{1a}{1p},$$
and
$$\frac{(ap)^2}{(1p)^2}\frac{1a}{a}\,n\to\infty. \tag{1}\label{1}$$
In particular, condition \eqref{1} will hold if $p\in(0,1)$ is fixed and $(1a)n\to\infty$ and $(ap)^2 n\to\infty$.
If $n\to\infty$, $1>a>p>0$, $k:=an$ is an integer, $(1a)n=O(1)$, and $p$ is fixed (or, more generally, $(1a)p/(1p)\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(1p)^{nk} \sim\frac{(np)^k}{k!}\,(1p)^{nk}.$$
If $p\in(0,1)$ is fixed and $n\to\infty$ and $(ap)^2 n=O(1)$, then, by the central limit theorem, $$P(S_n\ge an)\sim P\Big(Z\ge(ap)\sqrt{\frac n{p(1p)}}\,\Big),$$ where $Z\sim N(0,1)$.
The three cases considered above provide a complete description of the asymptotic behavior of the righttail 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 lefttail probabilities $P(S_n\le an)$, with $1>p>a>0$.
My paper here (Adv. Appl. Prob., 21 (1989) 475478), 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.

$\begingroup$ Your result is very nice. However, it does not seem to give a negligible relative error when $x\to\infty$ but $\sigma x\not\to\infty$. $\endgroup$ Dec 1, 2022 at 14:44

$\begingroup$ Also, I started reading the proof of your Theorem 2. For $k=n$, I get $E(n)=\sigma \ln(xY(x))$ instead of your $E(n)=x \ln(xY(x))$. $\endgroup$ Dec 2, 2022 at 0:59

$\begingroup$ @IosifPinelis On your first comment, thanks, I simplified too much and fixed it now. On your second comment, I need to work on it; it has been a long time. $\endgroup$ Dec 2, 2022 at 2:24

$\begingroup$ @IosifPinelis I couldn't figure it out then by a miracle I found my 34yearold notes. At $k=n$, we have $x=\sqrt{qn/p}=\sigma/p\ge \sigma$. Also, $xY(x)<1$ for $x>0$. So $x\ln(x Y(x))$ is an upper bound on $\sigma\ln(x Y(x))$. I'm not sure why I didn't use the smaller bound, probably something to do with how the induction works. $\endgroup$ Dec 2, 2022 at 3:06