Lower bound for sum of binomial coefficients?

Question

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!

Answer 1

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 .

Answer 2

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.

Answer 3

Here is a relevant paper:

T. Worsch, 1994. Lower and upper bounds for (sums of) binomial coefficients

Answer 4

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

Answer 5

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

Answer 6

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

Answer 7

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

Answer 8

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