Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Hi! I'm new here. It would be awesome if someone knows a good answer.

Is there a good lower bound for the tail of sums of binomial coefficients? I'm particularly interested in the simplest case $\sum_{i=0}^k {n \choose i}$. It would be extra good if the bound is general enough to apply to $\sum_{i=0}^k {n \choose i}(1-\epsilon)^{n-i}\epsilon^i$.

For the more commonly used upper bound, variants of Chernoff, Hoeffding, or the more general Bernstein inequalities are used. But for the lower bound, what can we do?

One could use Stirling to compute $n!$ and then ${n \choose k}$ and then take the sum:

${n \choose k} = \frac{n!}{k!}{(n-k)!}$, and Stirling's formula (a version due to Robbins) gives $$n! = \sqrt{2\pi}n^{-1/2}e^{n-r(n)}$$ with remainder $r(n)$ satisfying $\frac{1}{12n} \leq r(n) \leq \frac{1}{12n+1}$.

For the next step, it's easy to apply Stirling thrice. But, even better, I noticed that Stanica 2001 has a slight improvement to the lower bound that also is simpler to state (but more difficult to prove):

$${n \choose k} \geq \frac{1}{\sqrt{2\pi}}2^{nH(k/n)}n^{1/2}k^{-1/2}(n-k)^{-1/2}e^{-\frac{1}{8n}}$$

for $H(\delta) = -\delta \log \delta -(1-\delta)\log(1-\delta)$ being the entropy of a coin of probability $\delta$.

Now for step 3. If $k$ is small, it's reasonable to approximate the sum by its largest term, which should be the ${n \choose k}$ term unless $\epsilon$ is even smaller than $k/n$. So that's great, we're done!

But wait. This bound is off by a factor of at most $\sqrt{n}$. It would be better to be off by at most $1 + O(n^{-1})$, like we could get if we have the appropriate Taylor series. Is there a nice way to do the sum? Should I compute $\int_{0}^{k/n} 2^{nH(x)}\frac{1}{\sqrt{2\pi}}x^{-1/2}(1-x)^{-1/2}n^{1/2}e^{-1/8n} dx$ and compare that to the discrete sum, and try to bound the difference? (This technique has worked for Stirling-type bounds.) (The terms not dependent on $k$ or $x$ can be moved out of the integral.)

Another approach would be to start from Chernoff rather than Stirling (i.e. "How tight is Chernoff guaranteed to be, as a function of n and k/n?")

Any ideas or references? Thanks!

share|improve this question
    
The terms in your sum do not depend on the index $i$. You might want to proofread what you wrote. –  Felipe Voloch Feb 16 '11 at 7:40
    
@cscjb: (Typo.) The first appearance of the entropy $H$ should read $H(k/n)$ and not $H(k)$, I think. –  Did Feb 16 '11 at 8:10
    
Thanks to both of you -- fixed. –  user13006 Feb 16 '11 at 13:11
    
Mert sent me a message and asked for the Stanica paper title. It is "Good lower and upper bounds on binomial coefficients", J. Inequal. in Pure and Appl. Math volume 2 #3, 2001. –  user13006 Sep 23 '11 at 3:10

7 Answers 7

up vote 5 down vote accepted

First, what the Stirling bound or Stanica's result give is already a $(1+O(n^{-1}))$ approximation of $\binom nk$, hence the only problem can be with the sum. I don't know how to do that with such precision, but it's easy to compute it up to a constant factor by approximating with a geometric series:

$$\sum_{i\le k}\binom ni=\begin{cases}\Theta(2^n)&k\ge n/2-\sqrt n,\\\\\Theta\left(\left(1-\frac{2k}n\right)^{-1}\binom nk\right)&k\le n/2-\sqrt n.\end{cases}$$

More generally,

$$\sum_{i\le k}\binom ni(1-\epsilon)^{n-i}\epsilon^i=\begin{cases}\Theta(1)&k\ge\epsilon n-s,\\\\\Theta\left(\frac{\epsilon(n-k)}{\epsilon n-k}\binom nk(1-\epsilon)^{n-k}\epsilon^k\right)&k\le\epsilon n-s,\end{cases}$$

where $s=\sqrt{n\epsilon(1-\epsilon)}$. Cf. the appendix to my paper http://math.cas.cz/~jerabek/papers/wphp.pdf .

share|improve this answer
    
You're right. I spoke too soon after waking up. The problem is that the $f(x) = x^{1/x}$ term is immediately multiplied by an $f(\frac{x}{x-1})$ term, and while a single $f(x)f(x/(x-1))$ term is maximized for $x=2$, optimizing sums over this product is not as clear. And if you can't precisely estimate the base of an exponential term, you're in trouble. Your approach is better -- and simple too! In retrospect it's the obvious thing to do. So I see it's covered by Proposition A.4 in your paper, with some slightly different notation. –  user13006 Feb 16 '11 at 16:51
    
So, more detail: geometric series comes from $${n \choose k-1}/{n \choose k} = \frac{k}{n-k+1} > \frac{k-i}{n-k+i+1}$$ Let $x = \frac{k}{n-k+1}$. Then $x \leq \frac{2k}{n}$, and $x > \frac{k-i}{n-k+i+1}$ for $k \geq i > 0$, so geometric series gives lower bound. $$\sum_{i=0}^{k} {n \choose i} \leq {n \choose k} \sum_{j = 0}^{k} x^j \leq {n \choose k}/(1-x)$$ matches your statement for $x = \frac{2k}{n}$. But I believe you must have intended to use $x = \frac{k}{n-k}$ or $\frac{k}{n-k+1}$, since otherwise it is not tight. Setting $\epsilon = 1/2$ in your 2nd version gives correct version. –  user13006 Feb 16 '11 at 16:54
    
I just simplified the expression since there are constant factors missed anyway. Taking $x=k/(n-k+1)$ gives $1-x=(n-2k+1)/(n-k+1)$. However, $n-k+1=\Theta(n)$ by the assumptions, hence $(n-2k+1)/(n-k+1)=\Theta((n-2k)/n)=\Theta(1-2k/n)$. Also, note that this argument gives an upper bound on the sum. The matching lower bound is slightly more complicated to prove, you basically need to show that $(k-i)/(n-k+i+1)$ is not too smaller than $k/(n-k+1)$ for sufficiently many $i$'s so that it works out. –  Emil Jeřábek Feb 16 '11 at 17:28
    
I should probably also point out that the extra terms are relevant only when $k$ is close to $n/2$. If $k\le\alpha n$ for some constant $\alpha<1/2$, then it all boils down to $\sum_{i\le k}\binom ni=\Theta\left(\binom nk\right)$, as Anthony Quas wrote in his answer. –  Emil Jeřábek Feb 16 '11 at 17:33
    
Thanks again. You're right of course. This turned out to be much easier than I anticipated. I think I was so excited to see the latex typeset in real-time that I followed up too soon. I do need the case where the terms are relevant, so I'm happy to know how to do that now. –  user13006 Feb 17 '11 at 19:13

In my paper "On Littlewood's estimate for the binomial distribution", Adv. Appl. Prob., 21 (1989) 475-478, copy at http://cs.anu.edu.au/~bdm/papers/littlewood2.pdf , I find sharp exact bounds on this sum (take the case $p=1/2$ in Thm 2 for your problem). The relative error is at most $O(n^{-1/2})$ for all $k$, better if $k$ is not close to $n/2$.

Somewhere on the arXiv there is a paper making numerical comparisons of many such approximations. I can't find it just now, maybe someone else can.

share|improve this answer
    
Brendan, Thanks. You might be referring to this: Central Binomial Tail Bounds, Matus Telgarsky, 2009. arxiv.org/abs/0911.2077v2 At this point I'd rather avoid the normal distribution and erf(), but I understand it's certainly useful, and it seems that it's hard to get a tight lower bound without it. –  user13006 Sep 23 '11 at 3:07

Do you know how good you need it? Provided $k < n/3$ say, a reasonable bound (correct to within a multiplicative factor of 2) is obtained by taking the last term $\binom {n}{k}$ (you see this because you can compute the ratio of each term to the prior term and bound it above by 1/2. Now you can estimate the sum as a geometric series.)

For $\sum_{j < k} \binom{n}{j}a^j(1-a)^{n-j}$, bounding by the last term also works quite well as long as $k$ is a good bit smaller than $an$.

share|improve this answer
    
Honestly, I only need a bound off by a polynomial factor since the exponential ones dominate, so the original that I started with would be fine. But it's become a sort of personal quest to find the "real" answer -- since I use Chernoff so much, and I know Stirling can be made extremely tight, I thought there should be an answer. I figured it's also something that should be answered somewhere on mathoverflow. So, this is what I started with, but I'd like to be able to get $k$ close to $1/2$. –  user13006 Feb 16 '11 at 12:58

Here is a relevant paper:

T. Worsch. "Lower and upper bounds for (sums of) binomial coefficients". http://digbib.ubka.uni-karlsruhe.de/volltexte/181894

share|improve this answer
    
Yes! Lemma 2.3 and 2.4 in particular (and, less importantly but still a part, Lemma 2.8) is what is needed to get a tight bound. Interesting that $e^{1/e}$ makes an appearance (via $\min x^{1/x}$ of course). The paper only considers the sums (i.e. probability $1/2$), but with these issues resolved it should be easy to generalize to any $p$. The paper also gets $O(\ldots)$ bounds instead of determining the constants, but the constants can be determined using some of the bounds that Stanica, for example, cites. Looks great! –  user13006 Feb 16 '11 at 12:53
    
Note that the paper only approximates the sums up to a factor of $k$. –  Emil Jeřábek Feb 16 '11 at 13:39
    
indeed, I spoke too soon. Doing math immediately after waking up doesn't work so well. –  user13006 Feb 16 '11 at 17:07

If you are willing to compute a few binomial coefficients, then (n+1) choose k + (n+1) choose (k-2) + ... + (n+1) choose (k-2l) is a good lower bound even for small l. ( I'm assuing that your summand terms should have i's where they have k's.) Of course, how good depends on how close k is to n/2, in which case one can look at differences from 2^(n/2).

Gerhard "Ask Me About System Design" Paseman, 2011.02.15

share|improve this answer
    
Thanks, I'll have to fix that. And that's definitely an obvious place to start. So the Worsch paper mentioned below makes this more explicit ... in particular $k \approx n/e$ seems to be a point of inflection in some sense for a very precise analysis. –  user13006 Feb 16 '11 at 13:03

Summing binomial coefficients $\sum_{i=0}^k\binom{n}{i}$ can be seen as asking "how many binary strings are close to the length-$n$ all-zero string, differing in at most $k$ places?". One can generalize this to larger alphabets, and this almost captures your question on $\sum_{i=0}^k\binom{n}{i} (1-a)^{n-k}a^k$. So perhaps the coding theory community has more to say on this issue?

One place to start is this set of lecture notes by Venkat Guruswami:

http://www.cs.cmu.edu/~venkatg/teaching/codingtheory/notes/notes2.pdf

(see page 3).

share|improve this answer
    
Indeed, that's precisely the origin of the problem. I hadn't realized the connection between smaller epsilon and larger alphabets. Nice! That means the probabilities can be replaced by larger alphabets, so coding theory becomes relevant. (The lecture notes are also interesting to me for other reasons; there's been much progress in searching for more optimal codes in the last few years, so it's great to see Guruswami's notes from 2010. Thanks!) –  user13006 Feb 16 '11 at 13:07

Refer to paper: Approximations for the probability in the tails of the binomial distribution by I. Blake, H. Darabian. Might be useful.

share|improve this answer

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.