Good afternoon,

I would like to ask, if anyone knows how to evaluate a sum

$$\sum_{k=0}^{\lambda n}{n \choose k}$$

for fixed $\lambda < 1/2$ with absolute error $O(n^{-1})$, or better.

In Concrete Mathematics (Graham, Knuth, Patashnik), it is shown how to evaluate this sum with absolute error $O(1)$, but it is not clear to me, how to obtain better absolute error in a straightforward manner.

Thank you in advance.


This is more of an extended comment than an answer, but you may find it useful.

In Exercise 9.42 of Concrete Mathematics (page 492 in the second edition), the authors establish the asymptotic formula $$\sum_{k=0}^{\lambda n} {n\choose k}=2^{n H(\lambda)-\lg(n)/2+O(1)}$$ where $0<\lambda< 1/2$, $H(\lambda)= \lambda \lg({1\over \lambda})+(1-\lambda)\lg({1\over 1-\lambda})$, and $\lg$ is the binary logarithm.

The sum on the left is a small fraction of the full sum $2^n$. Note that this is a multiplicative approximation, the ratio of the sum and the approximation remains bounded as $n\to\infty$, not the difference.

Their result has an interpretation using probability. Write $$\sum_{k=0}^{\lambda n} {n\choose k} =2^n\,\mathbb{P}(X_n/n\leq \lambda)$$ where $X_n$ is a binomial$(n,1/2)$ random variable. The theory of large deviations suggests an approximation $$\mathbb{P}(X_n/n\leq \lambda)\approx \exp(-nI(\lambda))$$ where $I$ is the rate function $I(x)=x\log(x)+(1-x)\log(1-x)+\log(2)$. This gives the leading factor in their approximation; they also divide by $\sqrt{n}$ for further accuracy.

If you are willing to use the standard normal distribution function $\Phi(z)=\mathbb{P}(Z\leq z)$, then by the central limit theorem, we have $$ \mathbb{P}(X_n\leq \lambda n) =\mathbb{P}\left({X_n-n/2\over\sqrt{n/4}}\leq {\lambda n-n/2\over\sqrt{n/4}} \right) \approx\mathbb{P}\left(Z\leq \sqrt{n}(2\lambda-1) \right).$$ In other words, we have the approximation $$ \sum_{k=0}^{\lambda n} {n\choose k} =2^n\, \Phi(\sqrt{n}(2\lambda-1)).$$ This seems to be at least as accurate as the Concrete Mathematics approximation, and you can get more accuracy by using the "continuity correction".

More detailed asymptotic results for binomial tails can be found in this paper by Andrew Carter and David Pollard. In particular, see Theorem 1. I hope you find what you want there; happy hunting!

  • 3
    $\begingroup$ Let me mention that CLT cannot yield large deviations estimates. (I remember having explained that to Qiaochu on the site hence this part of your answer indirectly confirms the surprising extent of this confusion.) $\endgroup$ – Did Nov 26 '12 at 8:48
  • $\begingroup$ @Did Do you mean that CLT based approximations can only be sharp for $\lambda$ close to $1/2$, and not in the tail? $\endgroup$ – Thomas Ahle Sep 17 '15 at 22:44
  • $\begingroup$ @Byron Would it be possible to expand the O(1) from concrete mathematics further? $\endgroup$ – Thomas Ahle Sep 17 '15 at 22:54
  • $\begingroup$ @ThomasAhle What I mean is that, in the present context, CLT provides the asymptotics of $P(X_n\le n/2+\lambda\sqrt{n}/2)$ when $n\to\infty$ for every fixed $\lambda$, but that CLT says nothing about the asymptotics of $P(X_n\le n/2+\lambda_n\sqrt{n}/2)$ when $n\to\infty$ if $\lambda_n$ varies with $n$, especially if $\lambda_n\to\infty$ or if $\lambda_n\to0$. There are tools to deal with the latter, but CLT is not one of them. $\endgroup$ – Did Sep 18 '15 at 8:42

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.