Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

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!

share|improve this answer
1  
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.) –  Did Nov 26 '12 at 8:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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