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!
Best Answer
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 .