# Upper bound of sum of binomial coefficients

I am looking for an upper bound - up to constant factor - for:

$\sum_{k=t}^{t+l} {n \choose k} \cdot 2^{-n}$ where:

The values of $t$ are between: $\frac{n}2+\sqrt{n} \leq t \leq \frac{9n}{10}$. (The previous $\frac9{10}$ can be replaced by any other constant between $\frac12$ and 1 ...)

In my configuration, the $l$ (number of elements of the sum) can vary between: $1 \leq l \leq \sqrt{n}$

• Where does this problem come from? – Joonas Ilmavirta Oct 30 '14 at 14:10
• Approximate $\binom nt$ by Stirling, and the rest by a geometric series. – Emil Jeřábek Oct 30 '14 at 14:32
• I am trying to analyze some cryptographic protocol for coin tossing. I got some expression that contains that sum in it. Any way, the above question seems very basic to me. That sum is actually: $Pr[t \leq X \leq t+l]$ where $X$ is a random variable that counts the number of successes when throwing $n$ fair coins. For $t$ in $\frac{n}2 \leq t \leq \frac{n}2 + \sqrt{n}$ it easy to analyze, and for $t$ at the tail it's easy to give a good bound simply by taking the first element of the sum (and consider it as geometric series) – Nissan Levi Oct 30 '14 at 14:32
• A search for "binomial coefficient sum" here on MathOverflow gives many results, including question 55585: mathoverflow.net/questions/55585/… – The Masked Avenger Oct 30 '14 at 15:07
• I'm aware of question 55585, but it's not the same as mine. There he asks for bounds of the entire tail $Pr[t \leq X]$, where what I need is a bound for $Pr[t \leq X \leq t+l]$. Applying the technique that Emil suggests for $Pr[t \leq X]$ will give a simple expression of the form $\frac{1}{1-q}$ (where $q$ is the quotient of the geometric series), while in my situation I'll get: $\frac{1-q^l}{1-q}$ – Nissan Levi Oct 30 '14 at 15:30

Let me write $a\approx b$ for $a=\Theta(b)$, and $t=\frac n2(1+\tau)$.
Stirling approximation gives $$2^{-n}\binom nt=(1+o(1))\frac{n^n}{(2t)^t(2(n-t))^{n-t}}\sqrt{\frac n{2\pi t(n-t)}} \approx\bigl((1+\tau)^{1+\tau}(1-\tau)^{1-\tau}\bigr)^{-n/2}\frac1{\sqrt{n-t}}.$$ For any $t\le k<t+l$, we have $$\binom n{k+1}\binom nk^{-1}=\frac{n-k}{k+1}\le\frac{n-t}{t+1}\le\frac{1-\tau}{1+\tau},$$ hence $$\binom nt^{-1}\sum_{k=t}^{t+l}\binom nk\le\sum_{k=0}^l\left(\frac{1-\tau}{1+\tau}\right)^k=\frac{1+\tau}{2\tau}\left(1-\left(\frac{1-\tau}{1+\tau}\right)^{l+1}\right)\approx\frac1\tau\left(1-\left(\frac{1-\tau}{1+\tau}\right)^{l+1}\right).$$ Similarly, if we put $\tau'=\tau+2l/n$ so that $t+l=\frac n2(1+\tau')$, we have $$\binom n{k+1}\binom nk^{-1}\ge\frac{1-\tau'}{1+\tau'},$$ hence $$\binom nt^{-1}\sum_{k=t}^{t+l}\binom nk\ge\sum_{k=0}^l\left(\frac{1-\tau'}{1+\tau'}\right)^k\approx\frac1\tau\left(1-\left(\frac{1-\tau'}{1+\tau'}\right)^{l+1}\right),$$ where I’ve used the fact that $\tau\le\tau'\le2\tau$ due to the assumptions.
If $l\ge1/\tau\ge1/\tau'$, then $$\left(\frac{1-\tau}{1+\tau}\right)^{l+1}\le(1+o(1))e^{-2}<1,$$ and likewise for $\tau'$, hence both bounds reduce to $$\binom nt^{-1}\sum_{k=t}^{t+l}\binom nk\approx\frac1\tau.$$ On the other hand, if $l\le1/\tau\le2/\tau'$, then $$\left(\frac{1-\tau'}{1+\tau'}\right)^k\ge(1+o(1))e^{-4},\qquad k\le l,$$ hence $$\binom nt^{-1}\sum_{k=t}^{t+l}\binom nk\approx l.$$ Putting everything together, and using the fact that $n-t\approx n$ by assumption, we obtain $$2^{-n}\sum_{k=t}^{t+l}\binom nk\approx\frac{\min\{l,\tau^{-1}\}}{\sqrt n}\bigl((1+\tau)^{1+\tau}(1-\tau)^{1-\tau}\bigr)^{-n/2}.$$
• As I understand it, the approximation can be written as: $Pr[t \leq X \leq t+l]\ \leq\ l \cdot Pr[X=t]$. I'm afraid that for large $t$ ($t$ around $Const \cdot n$), and $l$ around $\sqrt{n}$ that approximation is too rough and it isn't up to constant factor. I think that the problem in the calculation is the assumption that $l \leq \frac1{\tau}$. If $l$ is around $\sqrt{n}$, it's not true. – Nissan Levi Nov 1 '14 at 9:23
• I do not assume $l\le 1/\tau$, I distinguish two cases depending on whether $l\le 1/\tau$ or $l\ge 1/\tau$. The bound is $\min\{l,1/\tau\}\Pr(X=t)$ if you want to write it like that. – Emil Jeřábek Nov 1 '14 at 10:56