5
$\begingroup$

Consider the sum

$\sum_{k=0}^{n_0} {n \choose k} \cdot \alpha^k$

where $\alpha \in \mathbb{R}$ arbritary, $n_0 < n$. So it looks like binomial theorem,

$\sum_{k=0}^n {n \choose k} \cdot \alpha^k = (1+\alpha)^n$

I would like to find an estimate $\sum_{k=0}^{n_0} {n \choose k} \cdot \alpha^k \geq c \cdot (1+\alpha)^n$ where $c$ is a constant one can calculate explicitely. I tried to use binomial theorem and symmetry, i.e. ${n \choose k} = {n \choose n-k}$ and things like that, but it didn't work. (I would like to apply the estimate in particular for $n_0 := \lfloor \frac{n}{2} \rfloor$.)

2 Answers 2

3

You can apply Chernoff Bound - It states $\sum_{i > \lfloor \frac{n}{2} \rfloor} \binom{n}{i} p^i (1-p)^{n-i} \ge 1 - e^{-\frac{n}{2p}(p-\frac{1}{2})^2}$.

If you write the sum in reverse and use the symmetry of binomial coefficients, you obtain

$\sum_{i < \lceil \frac{n}{2} \rceil} \binom{n}{i} p^{n-i} (1-p)^{i} \ge 1 - e^{-\frac{n}{2p}(p-\frac{1}{2})^2}$ or $\sum_{i < \lceil \frac{n}{2} \rceil} \binom{n}{i} (\frac{1-p}{p})^{i} \ge p^{-n}(1 - e^{-\frac{n}{2p}(p-\frac{1}{2})^2}) $

Choosing $p \in (0,1)$ such that $\frac{1-p}{p} = \alpha$ (assuming $\alpha > 0$), i.e. $p=\frac{1}{1+\alpha}$, we obtain

$\sum_{i < \lceil \frac{n}{2} \rceil} \binom{n}{i} \alpha^{i} \ge (1+\alpha)^{n}(1 - e^{-\frac{n}{8}\frac{(1-\alpha)^2}{(1+\alpha)}})$ So you can take the following $C$ that depends on $n$ and $p$, at least in the case $n_0=\lfloor \frac{n}{2} \rfloor$: $C=1 - e^{-\frac{n}{8}\frac{(1-\alpha)^2}{(1+\alpha)}}$

EDIT: By choosing $\alpha = \frac{p}{1-p}$ you can get the following upper bound: $\sum_{i \le \lfloor \frac{n}{2} \rfloor} \binom{n}{i} \alpha^{i} \le (1+\alpha)^{n} e^{-\frac{n}{8}\frac{(1-\alpha)^2}{\alpha(1+\alpha)}}$

EDIT 2: In general, if $\alpha>0$ and we divide your inequality by $(1+\alpha)^n$ we obtain: $\sum_{k\le n_0} \binom{n}{k} (\frac{\alpha}{1+\alpha})^{k} (\frac{1}{1+\alpha})^{n-k} \ge c$, so we want to bound the probability that among $n$ coin tosses, we got "Head" no more than $n_0$ times, where the probability for head is $\frac{\alpha}{1+\alpha}$. Under the condition $\alpha < 1$, I can replace that "8" in the denominator by "2", see Hoeffding.

1

I think you're going to have a hard time getting such an inequality. Suppose you were able to prove the existence of a constant $c$ such that $\sum_{k=0}^{\lfloor n/2\rfloor}\binom{n}{k}\alpha^k \geq c(1+\alpha)^n$ for all $\alpha>0$. Dividing this inequality by $\alpha^n$ would give $\sum_{k=0}^{\lfloor n/2\rfloor}\binom{n}{k}\alpha^{k-n}\geq c(1 + \alpha^{-1})^n.$ When $\alpha\to +\infty$, the right hand side of this expression tends to $c$, whereas the left hand side tends to $0$, a contradiction.

This shows the constant $c$ would have to depend on $\alpha$ (and quite probably $n$ and $n_0$ as well), which seems like it would make such an inequality useless, unless you are really just looking for a very computable expression for $c$.