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 k}$. It would be extra good if the bound is general enough to apply to $\sum_{i=0}^k {n \choose k}(1-\epsilon)^{n-k}\epsilon^k$.

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^{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!

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!