2

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

Nissan Levi
  • 23
  • 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: http://mathoverflow.net/questions/55585/lower-bound-for-sum-of-binomial-coefficients/ – 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
  • Yes, unlike that question you need to use finite geometric series here. Nevertheless it works like charm. If I have it right, you should get that the sum is up to a constant factor $((1+\tau)^{1+\tau}(1-\tau)^{1-\tau})^{-n/2}n^{-1/2}\min{l,\tau^{-1}}$, where $t=(1+\tau)n/2$. – Emil Jeřábek Oct 30 '14 at 15:46
  • Thanks Emil. Can you elaborate a little about how you got that expression ? – Nissan Levi Oct 30 '14 at 16:57
  • Did you try to work it out yourself? I’m busy at the moment, but I may post more details some time later if necessary. – Emil Jeřábek Oct 30 '14 at 17:35

1 Answers1

2

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

Emil Jeřábek
  • 44,710
  • 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 01 '14 at 09: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 01 '14 at 10:56