6
$\begingroup$

Context for my question: For one part of my thesis I try to find an upper bound for the error in the normal approximation of the binomial distribution following the standard proof of the De Moivre–Laplace theorem with Stirling's formula. To make it concrete: Let $B_n$ be binomially distributed and let $N$ have the standardized normal distribution. I want to find an upper bound for $$\epsilon_n = \sup_{a<b} \left|\mathcal P\left(a\le \frac{B_n-np}{\sqrt{np(1-p)}} \le b\right)-\mathcal P(a \le N \le b)\right|$$

I want to compare this error with the best known error estimation of the Berry-Essee theorem for the binomial distribution. So far I have only found a proof which shows that $\epsilon_n \in O\left(\frac 1{\sqrt n}\right)$. See this proof by Márton Balázs and Bálint Tóth (which also just considered $\left|\mathcal P\left(a\le \frac{B_n-np}{\sqrt{np(1-p)}} \le b\right)-\mathcal P(a \le N \le b)\right|$ without the supremum). Other proofs do not investigate the error at all (see for example this proof on Wikipedia).

My Question: Do you know any proof in a textbook / paper / article where the theorem by De Moivre and Laplace is proved with Stirling's formula and the total error is estimated? The value of any occurring constants in the error estimate shall also be calculated. Can you point me to this proof?

Update: I reasked the question on MO, see https://mathoverflow.net/questions/219253/finding-an-error-estimation-for-the-de-moivre-laplace-theorem-with-stirlings-fo

$\endgroup$
3
  • $\begingroup$ Your title is somewhat misleading. It made me thing you found an error in the theorem. $\endgroup$ Sep 16, 2015 at 23:01
  • $\begingroup$ @uniquesolution You are right! I changed it... better? $\endgroup$ Sep 16, 2015 at 23:07
  • $\begingroup$ - Excellent! Thank you :) $\endgroup$ Sep 16, 2015 at 23:35

3 Answers 3

3
$\begingroup$

In fact, it follows form Balazs and Toth's paper that $$ \sup_{a_n\le c<d\le b_n}\left|\mathcal P\left(c\le \frac{B_n-np}{\sqrt{np(1-p)}} \le d\right)-\mathcal P(c \le N \le d)\right| \le C \frac{|a_n|^3+|b_n|^3+1}{\sqrt{n}}. $$

On the other hand, by Chernoff's (or Berstein's, or Hoeffding's) inequality, for $x\ge b_n>p$ we have $$ \mathcal P\left(\frac{B_n-np}{\sqrt{np(1-p)}} \ge x\right) \le Ke^{-Kx^2}\le Ke^{-K b_n^2}, $$ and a similar inequality may be written for $x\le a_n<-p$. Moreover, $\mathcal P\left(|N| \ge x\right)\le Me^{-Mx^2}$. Therefore, taking $a_n = - c\sqrt{\log n}$, $b_n = c\sqrt{\log n}$ with $c>0$ large enough, we get $$ \sup_{a<b} \left|\mathcal P\left(a\le \frac{B_n-np}{\sqrt{np(1-p)}} \le b\right)-\mathcal P(a \le N \le b)\right| = \mathcal O\left(\frac{\log^{3/2} n}{\sqrt{n}}\right), $$ which is not sharp, of course, but at least uniform.

$\endgroup$
5
  • $\begingroup$ +1. A lower bound of the supremum is of order $1/\sqrt{n}$, as can be seen by looking at the jump of the probability involving $B_n$ at some $k\approx pn$, that is, for some $b$ close to zero (since the other term is continuous with respect to $b$). $\endgroup$
    – Did
    Sep 20, 2015 at 12:49
  • $\begingroup$ math.stackexchange.com/questions/1290246/… for a more detailed explanation of @Did's comment (@Did: Thanks at this point! ;-) ) $\endgroup$ Sep 21, 2015 at 11:08
  • 1
    $\begingroup$ @zhoraster: Thanks for your answer. You are right, but the proof of Balazs and Toth does not provide a value for the constant $C > 0$. I look for a proof where this constant is also calculated... $\endgroup$ Sep 21, 2015 at 11:11
  • $\begingroup$ I also am looking for exact (not asymptotic) formula for the upper bound. $\endgroup$
    – Veliko
    Jan 29, 2017 at 13:13
  • $\begingroup$ @Veliko, the constant is computable. Alternatively, you may have a look at Uspensky's book mentioned in Marty Cohen's answer. $\endgroup$
    – zhoraster
    Jan 29, 2017 at 17:53
2
+50
$\begingroup$

(Note: I had the wrong author. This is now corrected.)

IIRC, Uspensky's book "Introduction to Mathematical Probability" (published maybe 1937) has a proof of the central limit theorem with explicit bounds on the error term.

The result is quite complicated.

$\endgroup$
3
  • $\begingroup$ You mean Wacław Sierpiński, right? Unfortunately I have not found any book "Probability" on viaf.org/viaf/29595075 written by him ("Probability" means in Polish [Prawdopodobieństwo])(pl.wikipedia.org/wiki/Prawdopodobie%C5%84stwo). Also Google does not give useful results. Do you have a copy of this book? Is "Probability" the right title?! Sorry for those additional questions and thanks for your efforts! $\endgroup$ Sep 21, 2015 at 18:51
  • $\begingroup$ My apologies. I meant 􏰀􏰁􏰁􏰂 J􏰃V􏰃 Uspensky􏰄 "Introduction to Mathematical Probability". $\endgroup$ Sep 21, 2015 at 22:16
  • $\begingroup$ Finally I got a look on his proof. Unfortunately he uses the characteristic functions and not the Stirling formula. Anyway: Because his theorem will help me with my thesis I'll accept your answer. Thanks for your recommendation! $\endgroup$ Sep 25, 2015 at 12:13
0
$\begingroup$

The best two-sided inequalities for the binomial distribution function may be found in Theory Probab. Appl., 57(3), 539–544. (6 pages) A Complete Proof of Universal Inequalities for the Distribution Function of the Binomial Law Published online: 04 September 2013 Keywords binomial distribution function, two-sided estimates, corrected normal approximations Publisher: Society for Industrial and Applied Mathematics A. M. Zubkov and A. A. Serov https://doi.org/10.1137/S0040585X97986138 We present a new form and a short complete proof of explicit two-sided estimates for the distribution function $F_{n,p}(k)$ of the binomial law with parameters $n,p$ from [D. Alfers and H. Dinges, Z. Wahrsch. Verw. Geb., 65 (1984), pp. 399--420]. These inequalities are universal (valid for all values of parameters and argument) and exact (namely, the upper bound for $F_{n,p}(k)$ is the lower bound for $F_{n,p}(k+1)$). Such estimates allow to bound any quantile of the binomial law by two subsequent integers that it contains.

© 2013, Society for Industrial and Applied Mathematics

$\endgroup$
1
  • $\begingroup$ see also arXiv:1207.3838 $\endgroup$ Jul 31, 2018 at 13:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.