2
$\begingroup$

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

$\endgroup$
8
  • 1
    $\begingroup$ Where does this problem come from? $\endgroup$ Oct 30, 2014 at 14:10
  • 1
    $\begingroup$ Approximate $\binom nt$ by Stirling, and the rest by a geometric series. $\endgroup$ Oct 30, 2014 at 14:32
  • $\begingroup$ 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) $\endgroup$ Oct 30, 2014 at 14:32
  • $\begingroup$ A search for "binomial coefficient sum" here on MathOverflow gives many results, including question 55585: mathoverflow.net/questions/55585/… $\endgroup$ Oct 30, 2014 at 15:07
  • $\begingroup$ 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}$ $\endgroup$ Oct 30, 2014 at 15:30

1 Answer 1

2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Nov 1, 2014 at 9:23
  • $\begingroup$ 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. $\endgroup$ Nov 1, 2014 at 10:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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