20
$\begingroup$

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!

$\endgroup$
3
  • $\begingroup$ The terms in your sum do not depend on the index $i$. You might want to proofread what you wrote. $\endgroup$ Feb 16, 2011 at 7:40
  • $\begingroup$ @cscjb: (Typo.) The first appearance of the entropy $H$ should read $H(k/n)$ and not $H(k)$, I think. $\endgroup$
    – Did
    Feb 16, 2011 at 8:10
  • $\begingroup$ 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. $\endgroup$
    – user13006
    Sep 23, 2011 at 3:10

8 Answers 8

17
$\begingroup$

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 .

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – user13006
    Feb 16, 2011 at 16:51
  • $\begingroup$ 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. $\endgroup$
    – user13006
    Feb 16, 2011 at 16:54
  • $\begingroup$ 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. $\endgroup$ Feb 16, 2011 at 17:28
  • $\begingroup$ 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. $\endgroup$ Feb 16, 2011 at 17:33
  • $\begingroup$ 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. $\endgroup$
    – user13006
    Feb 17, 2011 at 19:13
9
$\begingroup$

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. Taking $p=1/2$ in Theorem 2 gives:

$$B(k; n,1/2) = \sigma \cdot b(k-1,n-1,{1/ 2})\cdot Y({k-n/2\over \sigma})\cdot \exp({E(k; n,1/2)\over \sigma})$$

where:

  • $b(k-1; n-1,1/2) = {1\over 2^{n-1}}{n-1\choose k-1}$
  • $B(k; n,1/2) = \sum_{j=k}^n b(j; n,1/2) = {1\over 2^n}\sum_{j=k}^n {n\choose j}$
  • $Y(x) = Q(x)/\phi(x)$, where:
    • $\phi(x) := {1\over \sqrt{2\pi}} e^{-x^2/2}$
    • $Q(x) := \int_{x}^\infty \phi(u) du $
  • $E(k; n,1/2)$ is the error term, which lies between 0 and $\min(\sqrt{\pi/8}, {\sigma/(k-n/2)})$.
  • $\sigma = \sqrt{n}/2$.

The relative error is at most $O(n^{-1/2})$ for all $k$, better if $k$ is not close to $n/2$.

The above requires $\frac n2\le k\le n$. For $0\le k\lt \frac n2$, use $B(k;n,p) = 1 − B(n-k+1; n, 1-p)$.

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – user13006
    Sep 23, 2011 at 3:07
4
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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$. $\endgroup$
    – user13006
    Feb 16, 2011 at 12:58
4
$\begingroup$

Here is a relevant paper:

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

$\endgroup$
3
  • $\begingroup$ 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! $\endgroup$
    – user13006
    Feb 16, 2011 at 12:53
  • $\begingroup$ Note that the paper only approximates the sums up to a factor of $k$. $\endgroup$ Feb 16, 2011 at 13:39
  • $\begingroup$ indeed, I spoke too soon. Doing math immediately after waking up doesn't work so well. $\endgroup$
    – user13006
    Feb 16, 2011 at 17:07
1
$\begingroup$

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).

$\endgroup$
1
  • $\begingroup$ 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!) $\endgroup$
    – user13006
    Feb 16, 2011 at 13:07
1
$\begingroup$

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

$\endgroup$
2
0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – user13006
    Feb 16, 2011 at 13:03
0
$\begingroup$

Let $X_1,\ldots,X_n$ be iid from $\mbox{Bernoulli}(\epsilon)$, with standard deviation $\sigma := (\epsilon(1-\epsilon))^{1/2}$. Define $S_n := \sum_{i=1}^n X_i$. Then by Berry-Esseen, we have $$ \sup_{t \in \mathbb R}|P(S_n - np \le t) - \Phi_\sigma(\sqrt{n}t)| = \mathcal O(n^{-1/2}), $$ where $\Phi_\sigma$ is the CDF of a centered normal distribution with variance $\sigma^2$.

Therefore, if $Q_\sigma := 1 - \Phi_\sigma$, then

$$ \begin{split} P(S_n \ge k) - P(S_n=k) &= P(S_n > k) = 1 - P(S_n \le k)\\ &=1 - P(S_n - np \le k-np)\\ &= Q_\sigma((k-np)n^{-1/2}) + \mathcal O(n^{-1/2}). % \\&= Q_\sigma(kn^{-1/2}-pn^{1/2}) + \mathcal(n^{-1/2}). \end{split} $$

Then you can use standard concentration / anti-concentration results for the normal distribution to get bounds in different regimes for $k$. For example, if $k \ge np - (n(c\log n))^{1/2}\sigma$ with $0 < c \le 1$, then using Hoeffding's inequality gives

$$ \begin{split} P(S_n \ge k) - P(S_n = k) &\le Q_1(c\log n) + \mathcal O(n^{-1/2})\\ &\le \mathcal O(n^{-c/2}) + \mathcal O(n^{-1/2})\\ &= \mathcal O(n^{-c/2}) \to 0. \end{split} $$

$\endgroup$

Your Answer

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

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