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

  • 1
    Where does this problem come from? – Joonas Ilmavirta Oct 30 '14 at 14:10
  • 1
    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
up vote 2 down vote accepted

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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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