5
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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 $\endgroup$
    – Luis Mendo
    Dec 1, 2022 at 12:31

3 Answers 3

4
$\begingroup$

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}

$\endgroup$
4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
4
  • $\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 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. $\endgroup$ Dec 2, 2022 at 3:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.