# 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?

• Related: 1, 2. If interested, I can give you more detailed information about the proved range of validity for the bounds mentioned in the questions Dec 1, 2022 at 12:31

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}

$$\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$$.

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.

• 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$. Dec 1, 2022 at 14:44
• 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))$. Dec 2, 2022 at 0:59
• @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. Dec 2, 2022 at 2:24
• @IosifPinelis I couldn't figure it out then by a miracle I found my 34-year-old 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. Dec 2, 2022 at 3:06