Prove partial binomial sum is order of magnitude lower than full sum.

Question

I have the following binomial summation:

$$S(\alpha) = \sum\limits_{j=0}^{S_{X_0}^{-1}(\alpha)} {n \choose j} (1+p)^j$$

Where $X_0$ is binomial with parameters $n$ and $0.5$ and $S_{X_0}^{-1}(\alpha)$ is its inverse survival function.

I need to prove that this summation is an order of magnitude lower than $(2+p)^n$ for any $0<\alpha <1$ and $p>0$. It has to have a bound like:

$$S(\alpha) < (2+p-c)^n$$

or similar (the $c$ can be any positive number including a function of $p$ and $\alpha$). If such a $c$ doesn't exist, then any other (elementary) increasing function that bounds it above as tightly as possible.

Let's take the simple case, $\alpha=\frac 1 2$. Then $S_{X_0}^{-1}(\alpha) = \left[\frac n 2\right]$

In other words we need to show:

$$\frac{\sum\limits_{j=0}^{[\frac{n}{2}]} {n \choose j} (1+p)^j}{(2+p)^n}=O(k^n)$$

for some $k<1$.

But I'm not sure how to prove this.

Note that if $p=0$, this is not the case as we would have for example: $S(.5)=\frac{2^n}{2}$

EDIT: The ultimate goals is to prove that for the $\beta$ in equation (1) below $\beta \to 0$ as $t \to \infty$.

So, it we can prove:

$$\beta = e^{-(2\lambda+\delta \lambda)t} \sum\limits_{n=0}^{\infty} \frac{(\lambda t)^n}{n!}\sum\limits_{j=0}^{[\frac n 2]} {n \choose j}\left(1+\frac{\delta \lambda}{\lambda}\right)^j < e^{-(2\lambda+\delta \lambda)t} \sum\limits_{n=0}^{\infty} \frac{(\lambda t)^n}{n!}(2+\frac{\delta \lambda}{\lambda}-\epsilon)^n$$

for some $\epsilon > 0$, that'll do it.

---

Note: Using Wolfram alpha, I get the following (https://www.wolframalpha.com/input/?i=sum+%28n+choose+j%29+%281%2Bp%29%5Ej%2C+j%3D0+to+n%2F2):

$$\sum\limits_{j=0}^{\frac n 2} {n \choose j}(1+p)^j = (2+p)^n-{n \choose {\frac{n}{2}+1}}(1+p)^{\frac{n}{2}+1}{}_2F_1(1,1-\frac{n}{2},\frac{n}{2}+2,-1-p)$$

By sterling's approximation, we get:

$${n \choose \frac{n}{2}} \overset{\sim}{=} \frac{2^{n+1}}{\sqrt{n}}$$

Now, if I can find a similar exponential -like approximation for the hypergeometric function..

---

Background:

I have the following expression for the false negative rate of the uniformly most powerful test applied to two Poisson processes when there is a difference in rates ($\lambda_1 = \lambda+\delta \lambda$) and with the false positive rate $\alpha=\frac 1 2$:

$$\beta = \lim_{t \to \infty}\sum\limits_{n=0}^{\infty} \sum\limits_{j=0}^{[\frac n 2]} \left(\frac{e^{-\lambda_1 t}(\lambda_1 t)^j}{j!}\right)\left(\frac{e^{-\lambda t}(\lambda t)^{(n-j)}}{(n-j)!}\right)$$

It's pretty clear that this must be $0$. Simplifying we get:

$$\beta =e^{-(2\lambda+\delta \lambda)t} \sum\limits_{n=0}^{\infty} \sum\limits_{j=0}^{[\frac n 2]} (\lambda t)^{n-j} (\lambda t + \delta \lambda t)^j \frac{1}{j!(n-j)!}$$

$$ =e^{-(2\lambda+\delta \lambda)t} \sum\limits_{n=0}^{\infty} \frac{(\lambda t)^n}{n!}\sum\limits_{j=0}^{[\frac n 2]} {n \choose j}\left(1+\frac{\delta \lambda}{\lambda}\right)^j \tag{1}$$

If the binomial summation inside was not an order of magnitude lower than $(2+\frac{\delta \lambda}{\lambda})^n$, we would get a constant term and not $0$ for the limit. For example, if it were $(2+\frac{\delta \lambda}{\lambda})^n$, we would get $1$.

This makes sense since the dominant terms in $(1+\frac{\delta \lambda}{\lambda})^j$ are getting excluded from the summation. However, not sure how to prove this.

---

EDIT: the following python code demonstrates this result.

import numpy as np
import matplotlib.pyplot as plt
def binom_partial_sum(n,p=.5):
    b_sum=0
    for j in range(int(n/2)+1):
        b_sum+=comb(n,j)*(1+p)**j
    return b_sum/(2+p)**n
sums = np.array([binom_partial_sum(i,p=0.2) for i in range(11,501,2)])
plt.plot(np.arange(11,501,2),sums)

Answer 1

I’m not too sure what you mean by “survival function” so I’ll replace it with the integer part of $n\alpha$.

First, let’s do the case $\alpha=1/2$ as a warm-up.

$S(1/2)<\sum_{k=0}^n{\binom{n}{k}}(1+p)^{n/2}=(2\sqrt{1+p})^n$.

Now, $2\sqrt{1+p} < 2+p$, as $4(1+p) < 4+4p+p^2$, so we are done.

Now, in the general case $1/2 < \alpha <1$, we only need to find some $k < 2+p$ such that $$S_{\alpha}=\sum_{n/2 < l < n \alpha}{\binom{n}{l}(1+p)^l}=o(k^n).$$

The sum is equal to $(1+p)^nT_n=(1+p)^n\sum_{\beta n < l < n/2}{\binom{n}{l}r^l}$ where $\beta=1-\alpha$ and $r=\frac{1}{1+p}$.

Now, notice that for $0 \leq l < n$, $\binom{n}{l}r^l \geq \binom{n}{l+1}r^{l+1}$ iff $l>b_n$, where $b_n$ is the smallest integer not below $\frac{rn-1}{1+r}$.

Assume for now $\beta < q:= \frac{r}{1+r}=\frac{1}{2+p}$, and that $n$ is large enough, so that $\beta n < b_n$ (the argument can be adapted to $\beta=q$ without too much trouble but notations and slight changes of indices).

It follows that $\binom{n}{b_n}r^{b_n} \leq T_n \leq n\binom{n}{b_n}r^{b_n}$. By Stirling, if $L(s)=-s\log{s}$ and $q=\frac{r}{1+r}$, it follows $\log{T_n}=n(L(q)+L(1-q)+q\log{r})+O(\log{n})$.

Now, $f=L(q)+L(1-q)+q\log{r}=\log{1+r}$. Therefore, there exists $C > 0$ such that $\frac{(1+r)^n(1+p)^n}{Cn^C} \leq S_{\alpha} \leq Cn^C(1+r)^n(1+p)^n$ with $(1+p)(1+r)=2+p$, so the result is false.

Now, if $\beta > q$, then as above, where $c_n$ is the smallest integer above $n\beta$, $\binom{n}{c_n}r^{c_n} \leq T_n \leq n\binom{n}{c_n}r^{c_n}$.

Thus by Stirling $\log{T_n}=O(\log{n})+n(\beta\log{r}+L(\beta)+L(1-\beta))$.

Now, $C:\beta \longmapsto \beta\log{r}+L(\beta)+L(1-\beta)$ has derivative $\beta \longmapsto \log{r}-\log{\beta}-1+\log{1-\beta}+1=\log{\frac{(1-\beta)r}{\beta}}$, which is negative on $[\beta,q)$, so $C(\beta) < C(q)=\log{1+r}$ and thus, $S_{\alpha}$ is up to a polynomial factor, bounded above by $e^{nC(\beta)}(1+p)^n$, with $e^{C(\beta)}(1+p) < (1+r)(1+p)=2+p$ and it works.